[백준/5427/파이썬] 불

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

5427번: 불

• 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다.
• 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다.
• 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다.
• 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.
• 빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

 

Question Analyze)

이 문제는, BFS/DFS의 전형적인 문제라기 보다는, 일종의 시뮬레이션 문제이다.

이 시뮬레이션이 선형적이지 않고, 상,하,좌,우로 쭉 퍼져나가는 형식이기 때문에, DFS/BFS를 이용한다고 보면 된다.

따라서, 여러가지 방법이 있겠지만, 불이 퍼지는 함수 , 상근이가 움직이는 함수  이렇게 따로 구현해서, 문제를 풀거다.

 

구현하기 까다로운 이유

  - 상근이는 불이 붙으려는 칸으로 가면, 타 죽기 때문에, 가면 안된다.

  - 우선, 같은 시간의 흐름 속에서, 두가지의 과정이 일어나야한다. 1초 안에 불퍼지고 -> 상근이가 움직이고. 

  - 이 부분을 어떻게 해결 했냐면, fire() 함수는, fq(불의좌표가 저장되어있는 덱)이 비어질 때까지가 아니라, fq에 들어있는 원소의 갯수 만큼만 딱 반복을 한다. 왜냐하면, 연속적으로 일어나는게 아니라, 불이 선형적으로 1초 -> 2초 -> 3초 순으로 일어나는 개념으로 통제하기 위해서.

 -  상근이가 움직이는 것도, 다 움직이고 나면 -> fire() -> 움직이고 -> fire 이런식으로 진행을 해야하므로, 얘는 2중 반복이 필요할거 같음. (dq가 다 비어질 때 까지, dq의 길이만큼) 

def moving(y,x,d):
    visited[y][x] =1
    dq.append((y,x,d))
    while dq:
        qlen= len(dq)
        while qlen:
            y,x,d=dq.popleft()
            for k in range(4):
                ny=y+dy[k]
                nx=x+dx[k]
                if is_valid_coord(ny,nx) and visited[ny][nx] ==0 and board[ny][nx] ==".":
                    dq.append((ny,nx,d+1))
                if not is_valid_coord(ny,nx):
                    print(d)
                    return
            qlen -=1
        fire()
    print("IMPOSSIBLE")
    return

 

그리고, 메인 쪽에서는, 상근이가 있던 위치는 "."으로 바꿔주고, 불 -> 이동 순으로 해준다.

왜냐하면, 상근이가 있던 자리에는 불이 올 수 있기 때문임.

for _ in range(T):
    M,N = map(int,input().split())
    board=[list(map(str,input().rstrip())) for _ in range(N)]
    visited=[[0]*M for _ in range(N)]
    fq=deque()
    dq=deque()
    #print(board)
    for i in range(N):
        for j in range(M):
            if board[i][j] == "@":
                sy,sx=i,j
                board[i][j] = "." # 상근이가 있던 자리는 .으로 바꿔주기.
            if board[i][j] == "*":
                fq.append((i,j))
    fire()
    # 첫번째는 불이 먼저 진행, (첫번째에 불이 입구에 붙어버리면, 못들어간다)
    moving(sy,sx,1)
    # 그 다음 움직여준다.

이렇게 생각해주고 , 제출했더니,pypy3 -> 메모리초과, python3 -> 시간초과가 뜬다.

 

수정된 코드

수정된 곳

1) fire,moving 함수에 while qlen,dqlen 구문 -> for문으로 바꿔서, 가독성 높임.

2) d로 직접 하나씩 세어줬던 부분 -> visited 정수형으로 선언한 김에, 그기에 기록해서, 출력해줬음.

 

import sys
from collections import deque
input = sys.stdin.readline
dx=(1,0,-1,0)
dy=(0,1,0,-1)


def is_valid_coord(y,x):
    return 0<=y<N and 0<=x<M

def fire():
    for _ in range(len(fq)):
        y,x = fq.popleft()
        for k in range(4):
            ny= y+dy[k]
            nx= x+dx[k]
            if (0<=ny<N and 0<=nx<M) and board[ny][nx] ==".":
                board[ny][nx] = "*"
                fq.append((ny,nx))

def moving(y,x):
    visited[y][x] =1
    dq.append((y,x))
    while dq:
        for _ in range(len(dq)):
            y,x=dq.popleft()
            for k in range(4):
                ny=y+dy[k]
                nx=x+dx[k]
                if is_valid_coord(ny,nx) and visited[ny][nx] ==0 and board[ny][nx] ==".":
                    dq.append((ny,nx))
                    visited[ny][nx] = visited[y][x] +1
                if not is_valid_coord(ny,nx):
                    print(visited[y][x])
                    return
        fire()

    print("IMPOSSIBLE")
    return

T = int(input())
for _ in range(T):
    M,N = map(int,input().split())
    board=[list(map(str,input().rstrip())) for _ in range(N)]
    visited=[[0]*M for _ in range(N)]
    fq=deque()
    dq=deque()
    #print(board)
    for i in range(N):
        for j in range(M):
            if board[i][j] == "@":
                sy,sx=i,j
                board[i][j] = "."
            if board[i][j] == "*":
                fq.append((i,j))
    fire()
    moving(sy,sx)