그래프 탐색

문제 https://www.acmicpc.net/problem/2001 2001번: 보석 줍기 첫째 줄에 n, m, K가 주어진다. 다음 K개의 줄에는 보석이 있는 섬의 번호가 주어진다. 다음 m개의 줄에는 각 다리에 대한 정보를 나타내는 세 자연수 a, b, c(1 ≤ c ≤ 100)가 주어진다. 이는 a번 섬과 www.acmicpc.net 풀이 방법 1194번 달이 차오른다, 가자와 비슷한 문제이다. 이 문제에서는 열쇠를 갖고 이동하는 것이 아니라 보석을 줍고 이동하며, 시작점으로 돌아왔을때 보석의 최대 개수를 출력해야한다. 1194번과 유사하게 보석이 최대 14개이므로 보유한 보석을 최대16,384 (1

문제 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 풀이 방법 2206번 벽 부수고 이동하기와 비슷한 문제이다. 이 문제에서는 벽을 부수는 것이 아니라 열쇠로 이동하면 열쇠를 획득하여 해당하는 문을 열 수 있는 것이 특징이다. 따라서 큐에 좌표와 갖고 있는 키 상태를 넣어줘야 하며, 방문도 마찬가지로 키를 갖고있는 상태에서 방문한 좌표를 체크해줘야한다. (3차원 공간) 키를 갖고 있는 것을 어떻게 표현해야할지가 ..

문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 방법 (1,1)에서 (N,M)까지의 거리를 구하는 문제이다. 시작점과 도착점까지의 거리를 구하는 미로탐색과 비슷한 문제로, BFS로 해결할 수 있다. 다만 이 문제는 미로의 벽 하나를 부술 수 있다는게 차이점이다. 그렇다면 기존의 BFS 알고리즘에 벽을 부쉈는지, 안부쉈는지에 대해 추가로 처리해줘야 한다. 따라서 탐색 노드를 좌표뿐만 아니라 벽을 부쉈는지 안부쉈..

문제 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 풀이 방법 미로탈출 문제와 유사하지만 '불' 개념이 추가되어 시간이 지남에 따라 이동할 수 없는 지역이 추가되는 것이 차이점이다. 상근이가 바깥으로 나가는건 BFS로 풀 수 있고 마찬가지로 불도 상하좌우 한칸씩 움직이기 때문에 BFS로 갱신해주면 된다. 다만 새로운 노드 탐색을 할때 원래는 현재 방문 노드에서 인접한 노드들만을 탐색한다. 하지만 이 문제에서는 불이 전체적으로 퍼지기 때문에 이 탐색 과정을..