백준 문제집 풀이 8

백준/문제집(유기)

백준 문제집 풀이 8 - BFS

황태건 2023. 10. 6. 00:49

백준 BaaaaaaaaaaarkingDog님이 제작하신 문제집을 사용합니다

링크 : https://www.acmicpc.net/workbook/view/7313

문제집: 0x09강 - BFS (BaaaaaaaaaaarkingDog)

www.acmicpc.net

무너져버린 코테 기초를 다시 쌓기 위해 유형별로 문제를 쭉쭉 밀기로 했다.

모든 문제를 풀고 필요할 경우 코멘트를 작성한다.

1926번 : 그림 → 자주 쓰는 변수명을 통일하자. Q, 현재 위치 cr, cc, 새위치 nr, nc.

일반적으로 그래프의 크기는 DFS로 계산하는데, 배열을 순회하면서 확인할 경우 BFS로도 계산 가능하다.

2178번 : 미로 탐색 → 0과 1만 저장하는 visited 대신 거리를 저장하는 dist 배열을 사용한다.

7576번 : 토마토 → multi source BFS, BFS 전 모든 시작점을 큐에 미리 넣어두기만 하면 된다.

BFS가 끝나면 day(위의 dist와 유사) 배열을 순회하며 가장 큰 값을 확인해 출력한다. 덜 익은 토마토가 day 값 0을 갖는 경우 벽에 막혀 익지 못했다는 뜻이므로 -1을 출력한다.

4179번 : 불! → 모든 불을 시작점으로 먼저 BFS를 하고, 지훈이 위치에서 다시 BFS를 돌린다.

어떤 지점과 지훈이 사이 거리가 불과의 최단거리보다 크거나 같으면 지훈이는 그 곳에 갈 수 없다. 불난 곳이 없을 경우 오류가 발생할 수 있으므로 처리를 해주자.

1697번 : 숨바꼭질 → 1차원 BFS를 구현해보자. 이동 방향은 이런 식으로 하면 코드가 간결해진다.

short dir[3] = { -1,1,0 };

for (int i = 0; i < 3; i++) {
    int nxt = cur + dir[i];
    if (nxt == cur) nxt *= 2;
    
    //...
    
}

1012번 : 유기농 배추 → 코멘트 없음

10026번 : 적록색약 → 색약과 非색약의 이동 조건이 다르다.

非색약은 현재 칸과 다음 칸의 색이 같아야 이동 가능하며, 색약은 두 칸의 색이 모두 파란색이 아니기만 하면 이동 가능하다. 유사한 BFS문을 두 번 작성해도 되지만 함수 포인터를 활용해 이동 조건만 바꿔주면 코드가 간결해진다.

7569번 : 토마토 → 앞의 토마토 문제가 3차원으로 확장됐다.

문제 흐름은 동일하지만 3차원 좌표 이동에 익숙해져야 한다. 배열을 면(높이) - 행 - 열 순서로 선언하는 편이 코드 작성에 유리할 것이다. 3방향으로 6가지 이동이 가능하니 이동 방향은 dir[6][3]이 된다.

7562번 : 나이트의 이동 → 이동 방향 정의가 중요하다. 문제에 제시된 이미지를 참고하자.

5427번 : 불 → 앞의 불! 문제와 동일하다.

2583번 : 영역 구하기 → 문제가 어렵진 않다. BFS 전에 입력받은 구간의 visited 값을 1로 바꿔놓으면 된다.

그러나 좌표 입력과 계산 방식이 보편적인 방식과 달라 스트레스를 유발한다. 항상 x값이 먼저, y값이 그 다음 입력된다는 점에 유의하자. 이 사실은 M, N 입력에도 적용된다.

2667번 : 단지번호붙이기 → 코멘트 없음

5014번 : 스타트링크 → U나 D의 값이 0이 될 수 있음에 유의하자.

2468번 : 안전 영역 → 맨 처음 입력받는 값은 높이와 관련이 없다.

비의 양이 가질 수 있는 값은 0 이상의 모든 정수이다. 지역 높이의 최댓값이 M이라고 할 때, 비의 양이 M 이상이면 영역의 개수는 항상 0이 된다. 따라서 비의 양을 0부터 M - 1까지 증가시키면서 매번 BFS를 수행하면 된다.

6593번 : 상범 빌딩 → 위의 토마토 문제와 마찬가지로 3차원 정의와 이동에 유의하자.

2206번 : 벽 부수고 이동하기 → 3차원 BFS 문제라고 생각해보자.

상하 이동에 '다음 위치가 벽이고 현재 층이 0일 때 딱 한번 아래로 이동할 수 있다' 라는 제약을 두면 된다.

9466번 : 텀 프로젝트 → DFS로 푸는 걸 권장한다. 시간 초과를 피하기 위해 앞의 DFS 결과를 활용하자.

힌트

DFS 중 다음 정점이 이미 사이클 유무가 확정된 정점이라면, 현재까지 방문한 모든 경로에서 사이클이 생길 수 없다라는 점을 이용해아 한다. 사이클이 있고 없고는 상관없다.

유의해야 할 케이스는 DFS 중 아직 사이클 유무는 확정되지 않았지만 ( = 이번 DFS에서 처음 방문하지만) DFS 최초 시작점은 아닌 정점에서 사이클이 생기는 경우이다.

1
6
2 3 4 5 6 2

이 케이스를 고려하지 않으면 틀리는 건 당연하고 무한루프가 발생해 시간/메모리 초과가 뜰 수도 있다.

따라서 '이번 DFS에서의 방문 여부'를 기록할 배열을 추가로 사용해야 할 것이다.

2573번 : 빙산 → 햇수에 대한 정보를 잘 관리해야 한다.

힌트

1) 1년이 지나 전체 빙산의 높이가 갱신되면, 아직 다 녹지 않은 부분 중 하나를 골라 DFS를 수행한다. 해당 component의 크기를 녹지 않은 빙산의 전체 개수와 비교하면 빙산의 분리 여부를 확인할 수 있다.

'1년이 지났다'를 판단하기 위해서는 큐에 row, col 뿐만 아니라 year 정보도 저장해야 한다. 직전의 year값과 이번 원소의 year 값이 달라지는 순간 DFS를 수행하면 된다.

2) 빙산의 높이는 그때그때 갱신하되, 올해 전부 녹아버린 빙산은 인접 영역에 영향을 줄 수 없게 해야한다.

높이가 0이 된 햇수를 기록하는 별도의 배열을 사용해, 인접 영역의 높이가 0이여도 올해 녹아버린 빙산이라면 그냥 넘어가도록 했다. 코드로 나타내면 다음과 같다.

if (graph[nr][nc] == 1 || melted[nr][nc] == cy) //cy : 현재 햇수
	continue;

2146번 : 다리 만들기 → 2단계의 BFS가 필요하다. 섬을 구분하는 단계, 섬에서 다른 섬으로 이동하는 단계.

내가 푼 방식은 아래와 조금 다른데 아래 풀이가 더 직관적이고 깔끔한 것 같다.

1) 배열 전체를 순회하며, 처음 방문하는 '1'에서 BFS나 DFS를 통해 연결된 섬을 찾는다. 구분을 위해 별도의 배열에 섬 번호를 저장하자.

2) 섬을 찾았으면 해당 섬 전체 구간을 시작점으로 하는 BFS를 통해 '다른 섬'에 도달하기까지의 최단 거리를 구한다. '다른 섬'이란 번호가 아직 없거나 BFS 시작점과 섬 번호가 다른 '1'을 의미한다.

섬 내부에서의 이동은 거리가 변하지 않는다. 따라서 다른 섬에 도착했다면 그 지점에서 다시 BFS를 시작할 필요가 없다. 즉 도착한 지점은 큐에 넣지 않도록 해야 한다.

3) 새로 섬을 발견할 때마다 이를 반복한다. BFS를 통해 얻는 최단 거리들 중에서 가장 작은 값을 출력한다. 이 때 하나의 BFS가 끝났으면 번호 배열은 유지하되 BFS 거리 계산을 위한 dist 배열은 초기화해주자.

자꾸 틀린다면 각 섬에서 다른 지점까지의 최단 거리가 모든 지점에 대해서 잘 계산되고 있는지 확인해보자.

13549번 : 숨바꼭질 3 → 순수 BFS로 푸는 방법, 다익스트라 아이디어를 빌리는 방법이 있다.

아이디어를 빌리는 방법은, 이미 방문한 위치라도 거리가 더 짧을 경우 BFS에 추가해주면 된다.

순수 BFS로 푸는 방법은, BFS의 이동 방향을 논리적으로 확장하는 것이다. 그림으로 나타내보면 아래와 같다.

1600번 : 말이 되고픈 원숭이 → '벽 부수고 이동하기'와 비슷한 논리로 접근해보자.

이동 방향을 12개(상하좌우 4, 나이트 이동 8)로 설정하고, 아직 나이트 이동이 가능하면 12방향으로, 불가능하면 4방향으로 BFS 영역을 확장하도록 한다.

13913번 : 숨바꼭질 4 → 최적 경로를 찾는 문제는, 보통 path 배열을 사용하면 된다.

N부터 시작해 BFS로 이동 가능한 위치를 찾을 때마다 path[nxt]에 cur을 저장한다.

BFS가 끝나면 반대로 K부터 nxt = path[cur]를 반복해 끝에서부터 경로를 되돌아간다.

경로를 거꾸로 읽었으므로 스택이나 재귀함수 등을 사용해 순서를 뒤집어 출력하면 된다.

14442번 : 벽 부수고 이동하기 2 → 벽 부수고 이동하기 1번과 동일한 접근. 밑에는 깨달은 점

* 3차원 배열에서의 새로운 축은 f (floor)라고 통일하자

매번 이름 정하기 귀찮다

* dist 배열 전체를 -1로, 시작점만 0(이 문제에서는 1)으로 초기화하고 시작하자

경로 없는 경우와 시작점이 도착점인 경우 처리가 편리해진다. 또 시작점을 다시 방문하는 상황도 방지한다.

* 최솟값을 계산하되 경로가 없을 때 -1 출력하기 : 첫 번째 값에서 시작해 모든 위치 값 확인

최솟값 == -1 → 갱신

최솟값 >= 0 현재 위치의 값 == -1 → 무시

최솟값 >= 0 현재 위치의 값 >= 0 → 비교

16933번 : 벽 부수고 이동하기 3 → 이제는 4차원이다. 낮, 밤 정보까지 관리하자.

벽 부수고 이동하기 2에서 '현재 위치에 머무르는 경우'를 추가해주면 된다.

16920번 : 확장 게임 → multisource BFS로 풀면 된다. '이동 횟수'를 저장하기 위해 3차원으로 구현하자.

연산 횟수를 줄이기 위해서는 정확히 Si번 이동해 도착한 지점만 큐에 추가하면 된다.

만약 12% 정도에서 틀린다면 하나의 큐만 사용한 것은 아닌지 의심해보자.

3 4 2
2 1
1...
1..2
....

정답 : 9 3

하나의 공용 큐를 사용한 BFS로는 이 문제를 해결할 수 없다. BFS 시작 전 큐에는 {성 1 좌표1, 성 1 좌표2, 성 2 좌표}가 들어있다. 그런데 1번 성에서 주변의 빈 칸을 발견하면 그 칸의 좌표는 성 1 좌표 다음이 아닌 큐의 맨 끝에 추가된다. 따라서 두번 BFS를 수행하면 큐의 상태는 {성 2 좌표, 새로운 성 1 좌표, 새로운 성 1 좌표, ...}이 된다. 그러면 지금은 분명 성 1에서 BFS를 할 차례인데 그 위치를 성 2가 먼저 가져가버리게 된다.

따라서 우리는 P개의 큐를 생성해, 매번 큐1부터 큐P까지 큐에 들어있는 모든 원소를 시작점으로 하는 multisource BFS를 수행해야 한다. 무한루프를 방지하기 위해 매 BFS마다 새로 발견하는 영역의 수를 기록해, 큐1부터 큐P까지 반복을 마쳤는데 새로 발견한 영역이 없으면 종료한다.

11967번 : 불켜기 → '불 켜진 방에서 도달할 수 있는 방' 정보를 저장한다.

새로 '도달 가능' 체크한 방의 불이 켜져있을 경우, 큐에 추가해 해당 위치에서 탐색을 계속한다.

불을 새로 킨 방이 도달 가능한 경우, 큐에 추가해 해당 위치에서 탐색을 계속한다.

불 키기와 도달 체크의 순서를 신경쓰고, '새로'를 잘 구현해 무한루프를 방지하자.

17071번 : 숨바꼭질 5 → 플레 공포증으로 인한 스킵

9328번 : 열쇠 → 위의 '불켜기' 문제의 로직을 활용할 수 있다.

'문'을 만날 경우 '도달할 수 있음' 표시만 해둔다. 나중에 열쇠를 발견했을 때, 해당 열쇠로 열 수 있는 문 중 도달 가능한 문을 BFS 큐에 추가한다. 로직보다는 세세한 디테일에 신경써야하는 문제. 무엇보다 지도의 가장자리 부분을 잘 처리해줘야 한다. 가장자리에 있는 '빈 공간'과 '열쇠'와 '문서'는 모두 multisource BFS의 시작점이 된다. 또한, 가장자리에 있는 문은 모두 '도달할 수 있음' 처리를 하며, 거기다 이미 그 문의 열쇠를 갖고 있다면 BFS의 시작점으로 큐에 추가해야 한다.

3197번 : 백조의 호수 → 플레 공포증으로 인한 스킵

20304번 : 비밀번호 제작 → 플레 공포증으로 인한 스킵

푼 문제 : 27/30

총 소요 시간 : 11시간

<배운 내용>

BFS 뼈대 코드 확립

문제에 따라 visited와 dist 배열 선택

multisource BFS

component 찾기

n차원 BFS (변수 관리에도 사용될 수 있음)

최적 경로 찾기

'도달 가능' 여부만 표시해두고 잠금이 해제되면 그 때 이동하기