백준/ Gold 4 문제 , 백준 파이썬 5427 , 불 [BFS]

백준/ Gold 4 문제 , 백준 파이썬 5427 , 불 [BFS]

 

 

풀이 시간

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
반례들이 되게 많았던 문제 참고해서 풀어보시길

 

 

문제 출처

https://www.acmicpc.net/problem/5427

5427번: 불

 

 

 

반례

 

21
1 1
@

정답 = 1

---------------------------
3 3
.#.
#@#
.#.

정답 = IMPOSSIBLE

---------------------------
3 3
...
.@.
...

정답 = 2

---------------------------
3 3
.#.
#@#
.#*

정답 = IMPOSSIBLE

---------------------------
8 3
########
#*@.....
########

정답 = 6

---------------------------
5 6
##.##
#...#
#.#.#
#.#@#
#*#.#
#####

정답 = 5

---------------------------
5 6
##.##
#...#
#.#.#
#*#@#
#.#.#
#####

정답 = IMPOSSIBLE

---------------------------
5 6
##.##
#...#
#*#.#
#.#@#
#.#.#
#####

정답 = IMPOSSIBLE

---------------------------
8 9
########
#......#
#.####.#
#.#@.#.#
#.##.#.#
#....#.#
######.#
.......#
########

정답 = 28

---------------------------
5 3
##.##
#*.@#
#####

정답 = IMPOSSIBLE

---------------------------
7 7
.......
.*#.##.
.##.##.
...@...
.##.##.
.##.#*.
.......

정답 = IMPOSSIBLE

---------------------------
7 7
......*
.##.##.
.##.##.
...@...
.##.##.
.##.##.
*......

정답 = IMPOSSIBLE

---------------------------
7 7
.*....*
.##.##.
.##.##.
...@...
.##.##.
.##.##.
.*....*

정답 = 4

---------------------------
7 7
.......
*##.##*
.##.##.
...@...
.##.##.
.##.##.
*.....*

정답 = 4

---------------------------
7 7
*....*.
.##.##.
.##.##.
...@...
.##.##.
.##.##.
*....*.

정답 = 4

---------------------------
7 7
*.....*
.##.##.
.##.##.
...@...
.##.##.
*##.##*
.......

정답 = 4

---------------------------
7 7
..#.#..
.*#.#*.
.##.##.
...@...
.##.##.
.*#.#*.
.......

정답 = 4

---------------------------
7 7
.......
.*#.#*.
.##.###
...@...
.##.###
.*#.#*.
.......

정답 = 4

---------------------------
7 7
.......
.*#.#*.
###.##.
...@...
###.##.
.*#.#*.
.......

정답 = 4

---------------------------
7 7
.......
.*#.#*.
.##.##.
...@...
.##.##.
.*#.#*.
..#.#..

정답 = 4

---------------------------
5 3
..#..
.@#*.
..#..

정답 = 2

---------------------------

 

 

 

풀이

 

 

1. 기본세팅

 

1. 상하좌우 움직임

 

2. T번의 테스트 케이스

 

3. w,h 입력받기

 

4. h 행의 MAP 리스트 입력 받기

 

5. dq 초기화 (매 케이스마다 해주기)

 

 

 

2. BFS

 

하나의 while 문으로 해결하기 위해 dq 에는 사람과 불의 위치

 

dq1에는 사람의 위치만 담아준다.

 

dq1을 따로 만든 이유는 불의 위치는 계속 담기는데 dq1에 사람의 위치가 더 이상 담기지 않는 다면 그 테스트케이스는 사람이 탈출 할 수 없는 경우이므로 시간 절약을 위해 불을 더이상 이동 시키는 작업을 하지않고 바로 IMPOSSIBLE를 출력시키기 위함이다.

 

 

Tip!)

참고로 처음에 type(MAX[X][Y])==int 부분을 str(MAP[X][Y]).isdigit() 로 작성하였었는데, 이 부분 때문에 시간초과가 발생하였다. 지금의 타입이 int 인지 확인하는 코드가 훨씬 빠르므로 시간초과가 발생하지 않는다.

 

 

while 문을 하나로 돌리기 때문에 시작 위치가 불인지 사람인지 나눠주고 불은 벽이랑 불 자리를 제외한 위치로 이동,

 

사람은 길로만 이동시킨다.

 

이때 사람이 이동할때 따로 만들어 주었던 dq1에서 하나씩 지워줘야 바로바로 사람이 더 이동할 수 있는지 없는지를 체크해줄 수 있다.

 

각 사람이 이동하는 위치는 이전 이동횟수+1 로 할당한다.

 

만약 시작위치가 숫자이면서 각 끝 행쪽이나 열쪽이면 탈출을 이제 할 수 있으므로 해당 자리의 숫자를 리턴해주고 이외에는 다 IMPOSSIBLE 리턴이다.

 

 

 

여기서 중요한점은 dq에다가 appendleft를 사용해서 사람을 우선적으로 이동하게 해줬는데,

 

이렇게 하지 않으면

 

예제 1 번케이스

 

1
4 3
####
#*@.
####

 

이 경우에 사람은 오른쪽으로 이동할 수 있음에도 불이 사람을 지워버리면 연산이 수행되지않아 사람을 우선적으로 옮겨준다.

 

어차피 불은 벽이랑 불의 위치 빼고 모든 위치로 이동가능하여 불이 이동할 자리에 사람이 미리와있다면 지워버려 그 경로는 무효시킬수있다.

 

 

 

3. BFS 호출 및 처리

 

dq에는 불의 위치를 모두 담아주고 사람의 위치를 bfs에 넣어 호출한다.

 

이후 리턴값을 출력함.

 

 

정답

 

from collections import deque
import sys
input=sys.stdin.readline

dr=[(1,0),(0,1),(-1,0),(0,-1)]

for _ in range(int(input())):
    w,h=map(int,input().split())
    MAP=[list(input().rstrip()) for _ in range(h)]
    dq=deque()
    def bfs(x,y):
        dq1=deque()
        dq.appendleft([x,y])
        dq1.append([x,y])
        MAP[x][y]=1
        while dq:
            X,Y=dq.popleft()
            if len(dq1)==0:
                return "IMPOSSIBLE"
            if type(MAP[X][Y])==int:
                if X==0 or X==h-1 or Y==0 or Y==w-1:
                    return MAP[X][Y]
            for a,b in dr:
                mx,my=X+a,Y+b
                if 0<=mx<h and 0<=my<w:          
                    if MAP[X][Y]=='*':
                        if MAP[mx][my]!='#' and MAP[mx][my]!='*':
                            MAP[mx][my]='*'
                            dq.append([mx,my])
                    elif type(MAP[X][Y])==int:
                        if MAP[mx][my]=='.':
                            dq1.popleft()
                            MAP[mx][my]=MAP[X][Y]+1
                            dq.append([mx,my])
                            dq1.append((mx,my)) 
        return 'IMPOSSIBLE'
        
    for i in range(h):
        for j in range(w):
            if MAP[i][j]=='*':
                dq.append([i,j])
            elif MAP[i][j]=='@':
                x,y=i,j
                
    print(bfs(x,y))