파이썬 알고리즘 313번 | [백준 5427번] 불 - BFS (시간, 메모리 최적화 코드)

313. 불 (another version)

1) 어떤 전략(알고리즘)으로 해결?

• 하나의 큐에서 가장 먼저 불의 위치를 저장하고 마지막의 상근이의 위치를 저장하는 식으로 한 queue에서 이를 해결한다.
• 우선 불을 움직이고, 사람을 움직이는 순서로 진행한다.

2) 코딩 설명

<내 풀이>

 from collections import deque
import sys  

dirr = [-1,1,0,0]
dirc = [0,0,-1,1]

test_case = int(sys.stdin.readline().rstrip()) 
for t in range(test_case) : 
    w,h = map(int,sys.stdin.readline().rstrip().split())
    graph = [] 
    q = deque() 

    for i in range(h) : 
        graph.append(list(str(sys.stdin.readline().rstrip())))
        for j in range(w) : 
            if graph[i][j] == '*' : 
                q.append((i,j)) 
                graph[i][j] = "F" # 불 표시 
            elif graph[i][j] == '@' :
                graph[i][j] = 1 # 방문 표시 (방문한 곳은 숫자 & 내가 방문한 시간이 적힘)
                start = (i,j) 
    # 불 시작 지점 , 상근 시작 지점 순으로 담습니다.
    # 불 붙인 후 -> 상근이를 이동시키는 과정을 반복할 수 있게 하는 것입니다.  
    q.append((start))

    while q : 
        chkr, chkc = q.popleft()  
        fire_or_time = graph[chkr][chkc] 
        # 만약 탈출가능하면 당시 시간 (=정답) 출력하고, while 탈출합니다.
        if str(fire_or_time) != "F" and (chkc == 0 or chkc == w-1 or chkr == 0 or chkr == h-1): 
            print(graph[chkr][chkc])
            break
        # 상하좌우 탐색 
        for num in range(4) : 
            tmpr, tmpc = chkr+dirr[num], chkc+dirc[num]
            if 0<=tmpr<h and 0<=tmpc<w : 
                # 방문하지 않았고, 이동가능한 영역은 (".") 표시뿐인 영역이다. 
                # 이미 방문한 영역은 숫자가 기록, 불 붙은 곳은 "F"가 기록된 상황
                if graph[tmpr][tmpc]=='.' :  
                    # 1) 현재 꺼내온 것이 불이라면 
                    if fire_or_time == "F" : 
                        # 불을 붙입니다. 
                        graph[tmpr][tmpc] = "F" 
                    # 2) 상근이 위치라면 
                    else :
                        # 상근이가 도달한 시간을 기록합니다. 
                        graph[tmpr][tmpc] = fire_or_time+1 
                    q.append((tmpr,tmpc))

    # 벗어나지 못했다면 impossible 을 출력합니다.
    else : print("IMPOSSIBLE")

< 내 틀렸던 풀이, 문제점>

• 1. 12 프로에서 틀리는 문제

from collections import deque
import sys  

dirr = [-1,1,0,0]
dirc = [0,0,-1,1]

test_case = int(sys.stdin.readline().rstrip()) 
for t in range(test_case) : 
    w,h = map(int,sys.stdin.readline().rstrip().split())
    graph = []
    for i in range(h) : 
        graph.append(list(str(sys.stdin.readline().rstrip())))
    fireq = deque() 
    sgq = deque()

    for r in range(h) : 
        for c in range(w) : 
            if graph[r][c] == '*' : 
                fireq.append((r,c))
                # 처음 시간은 1초 
                graph[r][c] = 1
            elif graph[r][c] == '@' :
                graph[r][c] = 0
                sgq.append((r,c,1)) 

    # 1 ) 불 옮기기 
    while fireq : 
        chkr, chkc = fireq.popleft() 
        now_time = graph[chkr][chkc]
        for num in range(4) : 
            tmpr, tmpc = chkr+dirr[num], chkc+dirc[num]
            if 0<=tmpr<h and 0<=tmpc<w : 
                if graph[tmpr][tmpc]=='.' or graph[tmpr][tmpc]=='@' : 
                    # 불이 붙게 될 시간을 기록
                    graph[tmpr][tmpc] = now_time+1 # 불이 붙는 시간 
                    fireq.append((tmpr,tmpc))
                    

    # 2) 상그니 옮기기 (1초 부터 시작)
    # 옮김 가능 : 불이라면 시간이 time 보다 큰 경우에만  
    answer = int(1e9) 
    
    while sgq :  
        nowr, nowc, sg_time = sgq.popleft()  
        graph[nowr][nowc]=0 
        if nowr == 0 or nowr == h-1 or nowc == 0 or nowc == w-1 :   
            print(sg_time)
            break

        for num in range(4) : 
            tmpr, tmpc = nowr+dirr[num], nowc+dirc[num] 
            if 0<=tmpr<h and 0<=tmpc<w :
                if graph[tmpr][tmpc] == '.' : 
                        sgq.append((tmpr, tmpc, sg_time+1)) 
                elif graph[tmpr][tmpc]!='#' : 
                    if str(graph[tmpr][tmpc]).isdigit() and 0<int(graph[tmpr][tmpc]) and int(graph[tmpr][tmpc]) > sg_time:   
                    # 상그니가 이동할 수 있는 위치 & 이동 시간 
                        sgq.append((tmpr, tmpc, sg_time+1))
                        # graph[tmpr][tmpc] = 0

    else : print("IMPOSSIBLE")

• 반례

  불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 라는 문제 조건을 제대로 읽지 않았었다

1
3 3
*.*
.@.
*.*
output: 2
answer: IMPOSSIBLE

• 2. 메모리초과,시간초과

from collections import deque
import sys  

dirr = [-1,1,0,0]
dirc = [0,0,-1,1]

test_case = int(sys.stdin.readline().rstrip()) 
for t in range(test_case) : 
    w,h = map(int,sys.stdin.readline().rstrip().split())
    graph = []
    for i in range(h) : 
        graph.append(list(str(sys.stdin.readline().rstrip())))
    fireq = deque() 
    sgq = deque()

    for r in range(h) : 
        for c in range(w) : 
            if graph[r][c] == '*' : 
                fireq.append((r,c))
                # 처음 시간은 1초 
                graph[r][c] = 1
            elif graph[r][c] == '@' :
                graph[r][c] = 0
                sgq.append((r,c,1)) 

    # 1 ) 불 옮기기 
    while fireq : 
        chkr, chkc = fireq.popleft() 
        now_time = graph[chkr][chkc]
        for num in range(4) : 
            tmpr, tmpc = chkr+dirr[num], chkc+dirc[num]
            if 0<=tmpr<h and 0<=tmpc<w : 
                if graph[tmpr][tmpc]=='.' or graph[tmpr][tmpc]=='@' :
                    if not str(graph[tmpr][tmpc]).isdigit(): 
                        # 불이 붙게 될 시간을 기록
                        graph[tmpr][tmpc] = now_time+1 # 불이 붙는 시간 
                        fireq.append((tmpr,tmpc))
                        
    # 2) 상그니 옮기기 (1초 부터 시작)
    # 옮김 가능 : 불이라면 시간이 time 보다 큰 경우에만  
    answer = int(1e9)  
    while sgq :  
        nowr, nowc, sg_time = sgq.popleft()  
        graph[nowr][nowc]=0 
        if nowr == 0 or nowr == h-1 or nowc == 0 or nowc == w-1 :   
            print(sg_time)
            break

        for num in range(4) : 
            tmpr, tmpc = nowr+dirr[num], nowc+dirc[num] 
            if 0<=tmpr<h and 0<=tmpc<w :
                if graph[tmpr][tmpc] == '.' : 
                        sgq.append((tmpr, tmpc, sg_time+1)) 
                elif graph[tmpr][tmpc]!='#' : 
                    if str(graph[tmpr][tmpc]).isdigit() and 0<int(graph[tmpr][tmpc]) and int(graph[tmpr][tmpc]) > sg_time+1:   
                    # 상그니가 이동할 수 있는 위치 & 이동 시간 
                        sgq.append((tmpr, tmpc, sg_time+1))
                        # graph[tmpr][tmpc] = 0

    else : print("IMPOSSIBLE")

<반성 점>

• 문제 조건을 제대로 안 읽었던 점이 문제였다.
• 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 라는 구절을 잘 봤어야 했다.

<배운 점>

• 기존에는 불을 먼저 옮기고, 그 이후에 상근이를 옮기는 방식으로 했습니다.
• 이렇게 되면 불필요한 초 까지 고려해서