[백준] 5427 불

[백준] 5427번 불

그래프 / 너비우선탐색

 

 

 

[문제]

 

 

너비우선탐색인 bfs문제

불은 상하좌우로 증식하고 상근이는 상하좌우중 한군데로 이동가능한 것

 

그리고 하나 짚고 넘어가자면 '상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.'와 '상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다.'를 보면 불을 먼저 이동시키고난 후에 상근이를 이동시켜야 함을 알 수 있음!

 

생각보다 까다로웠다.

 

 

 

 

[과정]

 

내가 했던 풀이에서는 입력받은 배열(arr)의 외곽에 -1을 둘러서 상근이가 -1위치로 이동하게 되면 정답을 출력하는 형식이었다.

 

사실 이제와서 생각해보면 어차피 벽으로 둘러쌓여 있으므로 상근이가 배열(arr)의 인덱스를 벗어나면 정답을 출력해도 된다. 아마 거의 대부분이 이렇게 간단하게 하지 않았을까..?

전에 카카오 문제 '자물쇠와 열쇠'가 기억나서 그 영향으로 겁나 어렵게 생각한 것 같다.ㅋㅋㅋ

 

사람이 이동한 경로에는 배열의 값을 0으로 교환하여 나중에 해당 값이 알파벳인지 비교하여 visited를 대체하도록 구성했다.

가장 바깥의 while문을 돌 때마다 시간(result)에 1을 더해주면서 bfs를 계속 이어나가는 방식이다.

 

 

 

• 입력값을 배열에 저장하고 외곽에 -1을 더하여 새로운 배열로 만듬 
• 상근이의 위치, 불의 위치를 별도로 구해서 변수에 넣음
• bfs 수행
  • 사람의 이동경로를 나타내는 큐와 불의 이동경로를 나타내는 큐를 각자 설정
  • 다음에 이동할 사람의 이동경로가 있다면 수행
    • 불의 경로 이동
    • 한 타임에 저장된 불들의 개수만큼 반복하여 상하좌우로 증식
    • 이동경로가 '벽'이거나 '불'이거나 '-1'이라면 넘어가고 '.'과 사람의 이동경로의 경우에만 큐에 삽입후 이동
    • 사람의 경로 이동
    • 한 타임에 저장된 사람의 개수만큼 반복하여 상하좌우로 이동
    • 만약 다음 경로의 값이 -1이라면 이동시간을 리턴
    • 다음 경로의 값이 '.'이라면 방문하고 큐에 삽입 후 해당 배열의 인덱스 값을 0으로 바꾸어 방문표시
  • 만약 사람의 다음 이동경로가 없다면(갈 곳이 막힘) 'IMPOSSIBLE' 출력

 

 

 

 

[소스코드]

 

# 불

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

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(arr, x, y, fire):
    user_q = deque()
    fire_q = deque()
    user_q.append((x,y))
    arr[x][y] = 0

    # 불위치 큐에 넣기
    for fx, fy in fire:
        fire_q.append((fx,fy))

    result = 0   # 출력 값
    while user_q:
        
        # 불 이동
        for _ in range(len(fire_q)):
            fx,fy = fire_q.popleft()
            for i in range(4):
                nx = fx + dx[i]
                ny = fy + dy[i]

                if arr[nx][ny] == '#':
                    continue
                elif arr[nx][ny] == '*':
                    continue
                elif arr[nx][ny] == -1:
                    continue
                else:
                    arr[nx][ny] = '*'
                    fire_q.append((nx,ny))

        # 사람 이동
        user_cnt = 0
        for _ in range(len(user_q)):
            ux, uy = user_q.popleft()        
            for i in range(4):
                nx = ux + dx[i]
                ny = uy + dy[i]
                
                if arr[nx][ny] == -1:              
                    return result+1
                
                elif str(arr[nx][ny]).isdigit():
                    continue
                elif arr[nx][ny] == '#':
                    continue
                elif arr[nx][ny] == '*':
                    continue
                else:         
                    arr[nx][ny] = 0    # 방문함(표시)
                    user_cnt = 1
                    user_q.append((nx,ny))
        result += user_cnt

        if len(user_q) == 0:
            return 'IMPOSSIBLE'           

for _ in range(int(input())):
    n,m =  map(int, input().split())
    arr = [[-1]*(n+2)]
    
    for i in range(m):
        tmp = list(input().strip())
        tmp.insert(0,-1)
        tmp.append(-1)
        arr.append(tmp)
    arr.append([-1]*(n+2))

    fire = []    # 불의 위치
    for i in range(1,m+1):
        for j in range(1,n+1):  
            if arr[i][j] == '@':
                x = i     # 출발 위치
                y = j     # 출발 위치
            elif arr[i][j] == '*':
                fire.append((i,j))
    
    result = bfs(arr, x, y, fire)
    print(result)

 

 

 

---

 

[통과]

 

 

거의 3시간 걸려서 푼 것 같다..

풀고나니 필요없는 배열들도 보이고 단축시킬 수 있는 코드들도 많이 보인다.

계속 런타임에러가 발생해서 구글링을 통해 반례 케이스를 찾았다.

케이스를 올려놨으니 다른 사람들은 나보다 좀 더 편하게 푸시길..ㅠㅠ

그래도 자기전에 풀고 자서 편안~

 

 

---

※ 반례 테스트케이스

 

1
7 4
###.###
#.....#
#@....#
*######
답 : 5

1
3 3
..#
#@#
###
답 : 2

2
2 2
@*
..
4 4
####
@..#
*#..
*###

답 : 1

1
4 3
####
#*.@
####
답 : 1

1
3 3
###
#@.
##*
답 : IMPOSSIBLE

21
1 1
@
3 3
.#.
#@#
.#.
3 3
...
.@.
...
3 3
.#.
#@#
.#*
8 3
########
#*@.....
########
5 6
##.##
#...#
#.#.#
#.#@#
#*#.#
#####
5 6
##.##
#...#
#.#.#
#*#@#
#.#.#
#####
5 6
##.##
#...#
#*#.#
#.#@#
#.#.#
#####
8 9
########
#......#
#.####.#
#.#@.#.#
#.##.#.#
#....#.#
######.#
.......#
########
5 3
##.##
#*.@#
#####
7 7
.......
.*#.##.
.##.##.
...@...
.##.##.
.##.#*.
.......
7 7
......*
.##.##.
.##.##.
...@...
.##.##.
.##.##.
*......
7 7
.*....*
.##.##.
.##.##.
...@...
.##.##.
.##.##.
.*....*
7 7
.......
*##.##*
.##.##.
...@...
.##.##.
.##.##.
*.....*
7 7
*....*.
.##.##.
.##.##.
...@...
.##.##.
.##.##.
*....*.
7 7
*.....*
.##.##.
.##.##.
...@...
.##.##.
*##.##*
.......
7 7
..#.#..
.*#.#*.
.##.##.
...@...
.##.##.
.*#.#*.
.......
7 7
.......
.*#.#*.
.##.###
...@...
.##.###
.*#.#*.
.......
7 7
.......
.*#.#*.
###.##.
...@...
###.##.
.*#.#*.
.......
7 7
.......
.*#.#*.
.##.##.
...@...
.##.##.
.*#.#*.
..#.#..
5 3
..#..
.@#*.
..#..

답: 
1
IMPOSSIBLE
2
IMPOSSIBLE
6
5
IMPOSSIBLE
IMPOSSIBLE
28
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
4
4
4
4
4
4
4
4
2

1
5 6
##.##
#...#
#.#.#
#.#@#
#*#.#
#####
답 : 5