본문 바로가기

BFS2

[백준] - 2206. 벽부수고 이동하기 문제 풀이 이 문제는 예전에 BFS를 한창 풀었을 때에는 못 풀었던 문제였는데 이와 유사한 문제인 1600. 말이 되고픈 원숭이문제를 풀고 영감을 얻어서 다시 도전했더니 쉽게 풀렸다. 이 문제가 일반적인 BFS보다 까다로운 이유는 어떤 좌표에 올 수 있는 경우의 수가 2가지(이전에 벽을 부신 경우, 이전에 벽을 부수지 않은 경우)라는 점이다. 따라서 2차원 방문 배열로는 처리가 불가능하고 3차원 배열을 사용하여 문제를 해결하였다. 3차원 배열에서 0번쨰 인덱스는 벽을 이미 부수고 온 경우, 1번째 인덱스는 벽을 아직 부수지 않은 경우이다. bfs를 진행하며 다음의 3가지 경우에 대해서 처리해주었다. 현재 벽을 부술 수 있는 기회가 남아있고 다음 방문할 좌표가 벽인 경우, 기회를 소진하고 벽을 방문 기회가.. 2021. 3. 24.

[백준] 2146. 다리 만들기 문제 풀이 먼저 각 섬을 구분하기 위해 1이 아닌 수(2,3,4...)로 초기화 시켜주었다. 그런 다음 각 섬마다 탐색을 진행함에 있어 시작 집합을 섬의 경계 (주위에 0이 존재하는 칸)를 잡고 다른 섬을 만나기 전까지 bfs를 수행하면서 최소거리를 구하는 방식으로 진행했다. 여기서 distance가 증가하는 시점에 대해서 고민을 많이 했는데 아래 코드처럼 BFS의 Level을 판단하기 위해 초기 bounday의 사이즈를 구하고 이에 대해서 반복문을 도는 방식으로 Level을 판단했다. 그리고 초기 풀이는 50%가 넘어갈 때 메모리 초과가 발생했는데, BFS를 수행할 때 visited를 체크하지 않아서 많은 중복이 발생했던 것이 문제였다. 그리고 visited를 갱신하는 위치가 current의 시점에서 .. 2021. 2. 2.

이전 1 다음

티스토리툴바