(Python) 백준 3055번 : 탈출

출처 : https://www.acmicpc.net/problem/3055

3055번: 탈출

---

 

(Python) 백준 1055번 : 탈출¶

출처 : https://www.acmicpc.net/problem/3055

• 알고리즘 분류
  • BFS
  • 시뮬레이션

---

In [79]:

from collections import deque

In [80]:

def flow_water(array):
    x_queue = deque()
    for a,b in array:
        for i in range(4):
            na, nb = a+dx[i], b+dy[i]
            if not(0<=na<n and 0<=nb<m): continue
            if board[na][nb]=='.' and water_board[na][nb]==False:
                x_queue.append((na, nb))
                water_board[na][nb]=True
    return x_queue

In [81]:

def bfs(s_queue, water):
    time = 0
    while s_queue:
        queue = deque()
        time = time + 1
        water = flow_water(water)
        while s_queue:
            sx,sy = s_queue.popleft()
            for i in range(4):
                new_sx, new_sy = sx+dx[i], sy+dy[i]
                if not(0<=new_sx<n and 0<=new_sy<m): continue
                if water_board[new_sx][new_sy] == True: continue
                if board[new_sx][new_sy]=='X': continue
                if board[new_sx][new_sy]=='.' and water_board[new_sx][new_sy]==False and (new_sx, new_sy) not in visited:
                    visited.add((new_sx, new_sy))
                    queue.append((new_sx, new_sy))
                    continue
                if board[new_sx][new_sy]=='D':
                    return time
        s_queue = queue.copy()
        queue.clear()
    return 'KAKTUS'

In [82]:

if __name__ == '__main__':
    n,m = map(int, input().split())
    board = [list(input()) for _ in range(n)]

    water = deque()
    s_queue = deque()
    visited = set()
    water_board = [[False]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if board[i][j]=='*':
                water.append((i,j))
                water_board[i][j]=True
            elif board[i][j]=='S':
                s_queue.append((i,j))
                visited.add((i,j))
                board[i][j]='.'

    # 동 남 서 북
    dx = (0,1,0,-1)
    dy = (1,0,-1,0)
    print(bfs(s_queue, water))

3 6
D...*.
.X.X..
....S.
6