[C++] 백준 4179번 불!

그래프 탐색 문제.

최근에 이런 비슷한 문제인 3055번 탈출이라는 문제를 풀다가 실패했었다.

3055번: 탈출

아예 조건이 똑같던 문제였는데 불! 문제는 풀었었다. (오히려 정답률은 탈출이 높다..뭐지..?)

 

다른 사람들 풀이를 보니 조금 쉽게 접근한 거 같았다. 시간도 내가 훨씬 많이 걸리고 있었다.

다른 사람들 코드를 봐도 크게 다른 점은 못 찾았다. 아마 priority_queue를 custom해서 쓰는데, 이게 문제인 것 같았다.

queue 자료구조만 사용해서 풀어도 풀 수 있는 문제다.

 

문제 풀이

사실 문제 조건 자체는 간단하다.

• 불, 지훈이는 매 분마다 상, 하, 좌, 우로 움직일 수 있다.
• 지훈이는 불, 벽을 지나지 못하고 불은 벽을 지나지 못한다.
• 지훈이가 모든 칸의 가장자리에 도달하면 탈출을 할 수 있다.

탈출하는 최소 시간을 계산하면 된다.

매 분마다 불(들), 지훈이의 좌표에서 BFS를 진행해주면 된다.

 

시간이 많이 걸렸던 이유?

 

 

보면은 제일 최근에 맞았던 문제와 시간 차이가 3배가 나는 풀이가 있었다.

이는 내가 priority_queue를 써서

1. 거리가 적고
2. 불이 먼저 이동해야 하므로 알파벳 아스키코드가 작은 것

을 먼저 정렬하려 했다.

그런데 사실 의미가 없었다.

1번 조건인 거리가 적은 것은 어차피 bfs는 거리가 적은 것부터 진행이 된다. 따라서 그냥 큐를 써도 거리가 적은 것 먼저 탐색한다.

2번 조건인 불이 먼저 이동해야 하는 것은 BFS 큐에 불 좌표들을 먼저 넣어주면 된다. 그래서 따로 정렬시켜줄 필요가 없다.

 

문제의 예제 입력이 어떻게 진행되는지 살펴보고 테스트 케이스를 살펴보자.

 

4 4 #### #JF# #..# #..#

위 테스트 케이스의 정답은 3이다.

 

지훈, 불 시작 좌표에서 움직일 수 있는 곳 q에 넣어놓고 시작한다. (불 좌표들 먼저 넣어놓는다.)

그림 방향은

1->2->3

4->5->6이다.

가장자리에 도달하는 게 2분이고, 가장자리에서 나가는 것이 1분이 걸리므로 총 3분이 걸린다.

 

위처럼 진행되도록 코드를 짰다. 이제 코드를 살펴보자.

사용한 변수와 STL

BFS를 할 때 큐 자료구조를 쓰기위해 queue STL을 사용했다.

그리고 좌표 class Point를 만들었다. 해당 좌표까지 가는데 걸리는 시간 time, 해당 좌표가 무엇인지 저장하는 type, 그리고 (y, x) 좌표 변수가 있다.

근데 굳이 이렇게 안 만들고 풀 수도 있었을 것 같다.

위 클래스를 만든 이유가 나는 BFS를 하나의 큐에서만 진행하도록 설계했다. 따라서 지금 내가 진행하는 값이

불인지, 지훈인지 구분하기위해 위 클래스를 만들었다.

 

• width, height : 미로의 높이와 너비
• maze 배열 : 미로의 정보를 담는 배열
• visit 배열 : 해당 칸을 탐색했는지 여부를 저장하는 배열. [2]가 추가되었는데 [0]은 지훈이가 탐색했는지, [1]은 불이 탐색했는지 저장한다.
• fireQ 큐 : 시작할 때 입력받는 불 좌표들을 담아놓을 큐이다.
• jihoonY, jihoonX : 시작할 때 입력받는 지훈이의 좌표이다.
• direction 배열 : 상,우,하,좌 방향대로 이동하도록 좌표에 더하기만 하면 움직일 수 있도록 만든 배열이다.
• ans : 결과값이다. 0일경우 IMPOSSIBLE을 출력한다.

메인함수

처음에 높이와 너비를 입력받고, 미로의 각 칸이 무엇인지 입력받는다.

만일 'J'일 경우, 지훈의 좌표를 저장해놓고 해당 칸을 방문처리한다.

만일 'F'일 경우, 불 좌표를 저장하는 큐에 넣어놓고 해당 칸을 방문처리한다.

 

그리고 bfs 메서드로 미로를 탐색한 후에, ans값이 0이 아닐경우 ans값을 출력하고

0이라면 IMPOSSIBLE을 출력하도록 한다.

 

BFS 메서드 - 1

시작부분에 BFS용 큐 q를 만들어놓는다.

그리고 q에 불의 좌표들을 먼저 넣어놓는다.

그리고 마지막에 지훈의 좌표를 넣는다.

이렇게 해야하는 이유는 만일 지훈의 좌표가 불의 좌표보다 먼저 탐색할 경우,

조건이 성립되어 문제가 끝날수도 있기 때문이다. 

게시판에서 반례를 찾다가 알게되었는데,

F		F
	J
F		F

위 조건일 경우 J가 다른 불들보다 먼저 큐에 들어가면 가장자리에 오게되어 조건이 성립될 수 있다.

그런데 지훈은 불에 타기 전에 이동해야 한다. 위 조건은 IMPOSSIBLE이 정답이다.

따라서 불의 좌표가 지훈의 좌표들보다 먼저 이동할 수 있도록 해야한다.

 

BFS 메서드 - 2

그리고 BFS Q가 비지않을 때까지 BFS 탐색을 진행한다.

• curTime : 현재 칸까지 오는데 걸린 시간.
• curType : 현재 칸에 올 때, 지훈이 온 것인지 불이 온 것인지에 대한 정보
• curY, curX : 현재 칸의 좌표
• curTypeIdx : 0은 지훈, 1이 불

만일 탐색하는 현재 칸에 지훈이 왔는데 현재 칸이 'F'라면 같은 시간에 불이 났다는 뜻이다.

따라서 탐색하지 않고 다음 탐색을 진행한다.

 

만일 탐색하는 현재 칸에 지훈인데, 가장자리에 왔을 경우, 현재 칸까지 오는데 걸린 시간에 1분을 더해준 값을

ans에 저장하고 BFS 탐색을 종료한다.

 

그리고 상하좌우 탐색을 진행한다.

• 다음 칸의 idx가 정상적이고,
• 다음 칸을 현재 탐색중인 지훈 혹은 불이 이전에 탐색하지 않았고, 다음 칸이 벽과 불이 아니면

해당 칸을 탐색처리하고 큐에 집어넣는다.

 

맞았습니다 사진은 위에 있으므로 따로 또 올리진 않겠다.

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인이 가능하다.