수강한 강의
Part 3. 알고리즘 유형별 풀이
Chapter 02 알고리즘
- 그래프 탐색 (Graph Search, DFS & BFS) - 응용 편 2
학습 후기
그래프 탐색할 때 BFS를 사용하여 A에서 B까지 갈 수 있는지와 A에서 다른 경로까지의 최소 이동 횟수도 계산 가능하다. 단, 최소 이동 횟수만 말하는 거지 간선에 가중치가 포함되어 있다면 안된다. 최소 이동 횟수, 최단 시간 키워드가 존재하면 사용해볼 만하다.
1. https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
그래프 탐색 BFS를 이용한 가장 기본적인 문제로 시작점에서 끝 지점까지 벽이 아닌 길로 갈 수 있는 미로를 탐색하는 문제이다. 이 문제 정답의 최대치는 미로를 모두 갈 수 있는 경우 O(N^2)이며, BFS를 이용하면 다른 정점까지 가는 최소 이동 횟수도 계산할 수 있기에 BFS로 푼다. 격자형 그래프로 정점은 O(N^2), 간선은 O(N^2 * 4) BFS를 사용하므로 시간, 공간 복잡도는 모두 O(N^2)이다.
2. https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
어떻게 보면 그래프 문제로 보이지 않지만 하나의 상태를 하나의 정점으로 보고 점의 번호가 정점의 번호이고, 간선은 +1, -1, *2인 점을 향하는 방향성 간선으로 나타낼 수 있다. 1초 동안 이동하는 행위를 간선으로 나타내고 최소 개수로 간선 이동하는 방법을 가장 빨리 동생을 찾는 방법으로 두면 그래프 탐색을 이용하여 문제를 해결할 수 있다. 이때 정점은 O(10^5) 간선은 O(10^5 * 4) BFS를 사용하므로 시간, 공간 복잡도는 모두 O(N ^ 6)이다.
위 문제를 처음 풀 때는 +1, -1, *2에 대해서만 생각해서 BFS를 사용하여 풀어보았는데 메모리 초과로 공간 복잡도에서 에러가 났다. 생각해보니 visited를 체크 안 해줘서 O(N^3)의 복잡도로 문제를 풀었다. 이후에 visited와 dist를 사용하여 문제를 다시 풀어보니 해결되었다. BFS를 쓸 때 visited 체크를 잘하자.
수강 인증샷
패스트캠퍼스 [직장인 실무교육]
프로그래밍, 영상편집, UX/UI, 마케팅, 데이터 분석, 엑셀강의, The RED, 국비지원, 기업교육, 서비스 제공.
fastcampus.co.kr
본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.
'공부 > 패스트 캠퍼스 챌린지' 카테고리의 다른 글
| 코딩테스트 - 패스트캠퍼스 챌린지 35일차 (0) | 2022.02.27 |
|---|---|
| 코딩테스트 - 패스트캠퍼스 챌린지 34일차 (0) | 2022.02.26 |
| 코딩테스트 - 패스트캠퍼스 챌린지 32일차 (0) | 2022.02.24 |
| 코딩테스트 - 패스트캠퍼스 챌린지 31일차 (0) | 2022.02.23 |
| 코딩테스트 - 패스트캠퍼스 챌린지 30일차 (0) | 2022.02.22 |