난이도

Gold 4

풀이 참고 유무

?

막힌 부분

불과 사람을 동시에 bfs 진행하려고 했음

문제

문제 바로가기
상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.
각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)
다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.
'.': 빈 공간
'#': 벽
'@': 상근이의 시작 위치
'*': 불
각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

예제 입력

5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###

예제 출력

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

문제 검토

불과 사람이 동시에 BFS를 진행해야하고 불은 사람이 있는 곳에 갈 수 있지만 사람은 불과 불이 오려고 하는 곳도 갈 수 없다.

풀이(python)

Python

from collections import deque
n = int(input())
for _ in range(n):
    startrow=0
    startcol=0
    fire=[]
    col,row=map(int,input().split())
    matrix=[list(input()) for _ in range(row)]
    fire_visited=[[0 for _ in range(col)]  for _ in range(row)]
    human_visited=[[0 for _ in range(col)]  for _ in range(row)]
    #불과 사람의 시작위치 저장
    for x in range(row):
        for y in range(col):
            if matrix[x][y]=='@':            
                startrow=x
                startcol=y
            if matrix[x][y]=='*':
                fire.append([x,y])
    #불 BFS (일반적인 bfs)
    def fire_bfs():
        q=[]
        q=deque()
        for x in fire:
            q.append([x[0],x[1]])
            fire_visited[x[0]][x[1]]=1
        dx=[-1,1,0,0]
        dy=[0,0,1,-1]
        while q:
            r,c=q.popleft()        
            for mv in range(4):
                nr=r+dx[mv]
                nc=c+dy[mv]
                if nr<0 or nr>=row or nc<0 or nc>=col:
                    continue
                if fire_visited[nr][nc]>0:
                    continue
                if matrix[nr][nc]=='#':
                    continue
                fire_visited[nr][nc]=fire_visited[r][c]+1
                q.append([nr,nc])
    #사람 bfs (불이 도착한 시간보다 적을 때 q에 append하는 제약이 추가됨)                
    def human_bfs():   
        q=[]     
        q=deque()
        q.append([startrow,startcol])
        human_visited[startrow][startcol]=1
        dx=[-1,1,0,0]
        dy=[0,0,1,-1]
        while q:
            r,c=q.popleft()        
            for mv in range(4):
                nr=r+dx[mv]
                nc=c+dy[mv]
                if nr<0 or nr>=row or nc<0 or nc>=col:
                    return human_visited[r][c]
                    continue
                if human_visited[nr][nc]>0:
                    continue
                if matrix[nr][nc]=='#' or matrix[nr][nc]=='*':
                    continue
                #불이 번졌으면
                if fire_visited[nr][nc]!=0:
                	#불이 번진 시간 이상에 사람이 도착할 것 같으면 continue
                    if human_visited[r][c]+1 >= fire_visited[nr][nc]:
                        continue
                human_visited[nr][nc]=human_visited[r][c]+1
                q.append([nr,nc])
        return 'IMPOSSIBLE'            
    fire_bfs()    
    print(human_bfs())

동시에 진행하려고 했으나 굉장히 복잡하고 어려웠다.
그리고 불이 한 개도 아니고 불이 오려고 하는 곳을 체크해놓고 사람을 bfs 돌릴려니 굉장히 제약이 많았다.

이전에 토마토 문제에서는 여러 출발점에서 동시에 bfs를 돌렸는데 그건 토마토끼리 bfs를 동시에 돌린거라 어렵지 않았다.
하지만 불과 사람은 다르고 사람에게는 불과 불이 오는 곳에 오지 못한다는 조건이 있어서 더 복잡한 문제였다.

잠깐 서칭을 통해 불은 누구에도 제약받지 않고 불이 오는 시간보다 적은 시간에 사람이 도착하면 사람 또한 편하게 움직일 수 있다는 힌트를 얻었다.

그래서 불을 여러 위치에서 먼저 BFS를 돌리고 그 뒤 사람을 돌리되 불이 도착한 시간보다 적은 시간에만 도착하도록 했다.

걸린 시간

58:12

총평

BFS를 돌리려고 하는 대상이 둘 다 다른 대상이고 서로 조건이 다를 때는 우선 순위를 두어 따로 BFS를 돌리고 그 시간을 각각 기록하여 그것을 이용하여 해를 구한다.