백준 3055 파이썬 - 탈출

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

3055번: 탈출

문제

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 

코드

import sys
from collections import deque
from copy import deepcopy
r, c = map(int, sys.stdin.readline().split())
board = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(r)]
visited = [[0] * c for _ in range(r)]
dr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
water = deque()
for i in range(r):
    for j in range(c):
        if board[i][j] == 'S':
            hedgehog = [i, j]
        elif board[i][j] == '*':
            water.append([i, j])
def moveWater():
    length = len(water)
    while length:
        x, y = water.popleft()
        for m, n in dr:
            nx = x + m
            ny = y + n
            if 0 <= nx < r and 0 <= ny < c:
                if board[nx][ny] == '.':
                    board[nx][ny] = '*'
                    water.append([nx, ny])
        length -= 1
def bfs():
    q = deque()
    q.append((hedgehog[0], hedgehog[1], 1))
    visited[hedgehog[0]][hedgehog[1]] = 1
    while q:
        moveWater()
        length = len(q)
        while length:
            x, y, cnt = q.popleft()
            for dx, dy in dr:
                nx, ny = x + dx, y + dy
                if 0 <= nx < r and 0 <= ny < c:
                    if board[nx][ny] == 'D':
                        return cnt
                    if board[nx][ny] == '.' and not visited[nx][ny]:
                        visited[nx][ny] = 1
                        q.append((nx, ny, cnt + 1))
            length -= 1
    return 'KAKTUS'
sys.stdout.write(str(bfs()))

풀이

큐(deque)를 두개 생성해 하나는 물을 계속 옮겨주고 하나로는 고슴도치를 움직여준다.

틀린 코드

import sys
from collections import deque
r, c = map(int, sys.stdin.readline().split())
board = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(r)]
dr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
hedgehog = [[i, j] for i in range(r) for j in range(c) if board[i][j] == 'S']
water = [[i, j] for i in range(r) for j in range(c) if board[i][j] == '*']
def moveWater():
    array = []
    for i, j in water:
        for x, y in dr:
            nx = i + x
            ny = j + y
            if 0 <= nx < r and 0 <= ny < c:
                if board[nx][ny] == '.':
                    board[nx][ny] = '*'
                    array.append([nx, ny])
    for x, y in array:
        water.append([x, y])
def checkWater(nx, ny):
    for i, j in water:
        for x, y in dr:
            a = i + x
            b = j + y
            if 0 <= a < r and 0 <= b < c:
                if a == nx and b == ny:
                    return False
    return True
def bfs():
    q = deque()
    q.append((hedgehog[0][0], hedgehog[0][1], 1))
    while q:
        x, y, cnt = q.popleft()
        for dx, dy in dr:
            nx, ny = x + dx, y + dy
            if 0 <= nx < r and 0 <= ny < c:
                if board[nx][ny] == 'D':
                    return cnt
                if board[nx][ny] == '.':
                    if checkWater(nx, ny):
                        moveWater()
                        q.append((nx, ny, cnt + 1))
                        board[nx][ny] = ' '
    return 'KAKTUS'
sys.stdout.write(str(bfs()))