파이썬 알고리즘 197번 | [백준 4179번] 불 - bfs

197. 불

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

BFS

2) 코딩 설명

• 먼저 불을 붙인다, 불을 붙일 때 불이 붙는 시간으로 붙여놓는다
• 이후에 지훈이를 옮긴다

<내 풀이>

from collections import deque
import sys

r,c=map(int, sys.stdin.readline().rstrip().split())
map = [list(sys.stdin.readline().rstrip()) for _ in range(r)]
fq = deque() # 불큐
jq= deque()
rdis = [-1, 1, 0, 0]
cdis = [0, 0, -1, 1]

chk1=0; chk2=0

for rr in range(r) :
    for cc in  range(c) :
        #if chk1==1 and chk2==1:break
        if map[rr][cc]=='J' : 
            jrow=rr;jcol=cc;jcnt=1 # 위치와 time을 넣어주기
        elif map[rr][cc]=='F' : fq.appendleft((rr,cc, 1)) 

# #: 벽
# .: 지나갈 수 있는 공간
# J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
# F: 불이 난 공간


while fq : # 불 먼저 체크 (불이 도달하는 시간 기록)
        fnow = fq.pop()
        for f in range(4) :
            tmprf = fnow[0]+rdis[f]
            tmpcf = fnow[1]+cdis[f]
            if 0<=tmprf<r and 0<=tmpcf<c and \
                map[tmprf][tmpcf]=="." :
                    map[tmprf][tmpcf]=str(fnow[2]+1)
                    fq.appendleft((tmprf, tmpcf, fnow[2]+1))

# ['#', '#', '#', '#']
# ['#', 'J', 'F', '#']
# ['#', 3, 2, '#']
# ['#', 4, 3, '#']

impossible = True
visited=[[0]*c for _ in range(r)]
visited[jrow][jcol]=1
jq.append((jrow, jcol, 1))

while jq:

    now=jq.pop()
    #print("nowwwwwwww", now)
    row=now[0]
    col=now[1]
    cnt=now[2]

    if row==0 or col==0 or row==r-1 or col==c-1: #가장자리에 닿으면
        impossible=False
        # print(row, col, map[row][col])
        # print(cnt)
        #answer=cnt
        print(cnt);exit()
        #if cnt<mini:mini=cnt
    else :
        for j in range(4) :

            tmprj = row+rdis[j]
            tmpcj = col+cdis[j]
            
            if 0<=tmprj<r and 0<=tmpcj<c and \
                visited[tmprj][tmpcj]==0 :#and\

                if map[tmprj][tmpcj].isdigit() and \
                    int(map[tmprj][tmpcj])> cnt+1: # 불인 안
                        visited[tmprj][tmpcj]=1 
                        jq.appendleft((tmprj, tmpcj, cnt+1))
                elif map[tmprj][tmpcj]=="." :
                    visited[tmprj][tmpcj]=1 
                    jq.appendleft((tmprj, tmpcj, cnt+1))

if(impossible) : print("IMPOSSIBLE")

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

7% 에서 시간초과

from collections import deque
import sys
sys.setrecursionlimit(10**6)

r,c=map(int, sys.stdin.readline().rstrip().split())
map = [list(sys.stdin.readline().rstrip()) for _ in range(r)]
jq = deque() # 지훈큐
fq = deque() # 불큐

rdis = [-1, 1, 0, 0]
cdis = [0, 0, -1, 1]

# #: 벽
# .: 지나갈 수 있는 공간
# J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
# F: 불이 난 공간

for rr in range(r) :
    for cc in  range(c) :
        if map[rr][cc]=='J' : jrow=rr;jcol=cc;jcnt=1 # 위치와 time을 넣어주기
        elif map[rr][cc]=='F' : fq.append((rr,cc, 1))

while fq : # 불 먼저 체크 (불이 도달하는 시간 기록)
        fnow = fq.pop()
        for f in range(4) :
            tmprf = fnow[0]+rdis[f]
            tmpcf = fnow[1]+cdis[f]
            if 0<=tmprf<r and 0<=tmpcf<c and \
                map[tmprf][tmpcf]=="." :
                    map[tmprf][tmpcf]=str(fnow[2]+1)
                    fq.appendleft((tmprf, tmpcf, fnow[2]+1))

# ['#', '#', '#', '#']
# ['#', 'J', 'F', '#']
# ['#', 3, 2, '#']
# ['#', 4, 3, '#']

impossible = True

def dfs(row,col,cnt) :
    global impossible

    if row==0 or col==0 or row==r-1 or col==c-1: #가장자리에 닿으면
        impossible=False
        print(cnt);exit()
    
    else :
        for j in range(4) :

            tmprj = row+rdis[j]
            tmpcj = col+cdis[j]

            
            #print("cnt", cnt)
            if 0<=tmprj<r and 0<=tmpcj<c and \
                visited[tmprj][tmpcj]==0 and\
                map[tmprj][tmpcj].isdigit() and \
                    int(map[tmprj][tmpcj])> cnt:
                    
                    #print(tmprj, tmpcj, map[tmprj][tmpcj])
                    #print(tmprj, tmpcj)

                    visited[tmprj][tmpcj]=1 
                    dfs(tmprj, tmpcj, cnt+1)
                    visited[tmprj][tmpcj]=0

visited=[[0]*c for _ in range(r)]
visited[jrow][jcol]=1
dfs(jrow, jcol, 1)


if(impossible) : print("IMPOSSIBLE")

오잉 네임 에러!? ㅇㅁㅇ

• 내가 체크하는 것 조건 잘못 설정해서 jrow 가 선언되지 않는 경우 있었음 ㅋ

7% 시간초과 ㅠㅠ 반례는 다 맞으니 시간 줄이자

from collections import deque
import sys
sys.setrecursionlimit(10**6)

r,c=map(int, sys.stdin.readline().rstrip().split())
map = [list(sys.stdin.readline().rstrip()) for _ in range(r)]
fq = deque() # 불큐

rdis = [-1, 1, 0, 0]
cdis = [0, 0, -1, 1]

chk1=0; chk2=0

for rr in range(r) :
    for cc in  range(c) :
        if chk1==1 and chk2==1:break
        if map[rr][cc]=='J' : 
            jrow=rr;jcol=cc;jcnt=1;chk1=1 # 위치와 time을 넣어주기
        elif map[rr][cc]=='F' : fq.append((rr,cc, 1));chk2=1

# #: 벽
# .: 지나갈 수 있는 공간
# J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
# F: 불이 난 공간


while fq : # 불 먼저 체크 (불이 도달하는 시간 기록)
        fnow = fq.pop()
        for f in range(4) :
            tmprf = fnow[0]+rdis[f]
            tmpcf = fnow[1]+cdis[f]
            if 0<=tmprf<r and 0<=tmpcf<c and \
                map[tmprf][tmpcf]=="." :
                    map[tmprf][tmpcf]=str(fnow[2]+1)
                    fq.appendleft((tmprf, tmpcf, fnow[2]+1))

# ['#', '#', '#', '#']
# ['#', 'J', 'F', '#']
# ['#', 3, 2, '#']
# ['#', 4, 3, '#']

impossible = True
mini=999999

def dfs(row,col,cnt) :
    global impossible
    global mini

    if row==0 or col==0 or row==r-1 or col==c-1: #가장자리에 닿으면
        impossible=False
        #print(cnt);exit()
        if cnt<mini:mini=cnt
    
    else :
        for j in range(4) :

            tmprj = row+rdis[j]
            tmpcj = col+cdis[j]

            #print("cnt", cnt)
            if 0<=tmprj<r and 0<=tmpcj<c and \
                visited[tmprj][tmpcj]==0 and\
                map[tmprj][tmpcj].isdigit() and \
                    int(map[tmprj][tmpcj])> cnt+1:
                    
                    #print(tmprj, tmpcj, map[tmprj][tmpcj])
                    #print(tmprj, tmpcj)

                    visited[tmprj][tmpcj]=1 
                    dfs(tmprj, tmpcj, cnt+1)
                    visited[tmprj][tmpcj]=0

visited=[[0]*c for _ in range(r)]
visited[jrow][jcol]=1
dfs(jrow, jcol, 1)

if(impossible) : print("IMPOSSIBLE")
else : print(mini)

• dfs를 bfs로 풀어볼게 ㅠㅠ

70%에서 틀렸음

틀렸던 이유 :

• 지훈이가 갈 수 있는 길을 검사할 때 , 나는 온통 한번쯤은 불이 붙었을 것이라고 생각하고 불이 붙었던 MAP (숫자인 경우) 에만 지훈이가 옮길 수 있게 했었음

추가적으로 저는 아래 CASE들을 무시했었다가 아주 먼 길을 돌아왔습니다. 🤮
1. 불(F)이 여러 개일 수도 있다는 점
2. 불이 붙지 않는 "." 이 존재할 수도 있다는 점

from collections import deque
import sys

r,c=map(int, sys.stdin.readline().rstrip().split())
map = [list(sys.stdin.readline().rstrip()) for _ in range(r)]
fq = deque() # 불큐
jq= deque()
rdis = [-1, 1, 0, 0]
cdis = [0, 0, -1, 1]

chk1=0; chk2=0

for rr in range(r) :
    for cc in  range(c) :
        #if chk1==1 and chk2==1:break
        if map[rr][cc]=='J' : 
            jrow=rr;jcol=cc;jcnt=1 # 위치와 time을 넣어주기
        elif map[rr][cc]=='F' : fq.appendleft((rr,cc, 1)) 

# #: 벽
# .: 지나갈 수 있는 공간
# J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
# F: 불이 난 공간


while fq : # 불 먼저 체크 (불이 도달하는 시간 기록)
        fnow = fq.pop()
        for f in range(4) :
            tmprf = fnow[0]+rdis[f]
            tmpcf = fnow[1]+cdis[f]
            if 0<=tmprf<r and 0<=tmpcf<c and \
                map[tmprf][tmpcf]=="." :
                    map[tmprf][tmpcf]=str(fnow[2]+1)
                    fq.appendleft((tmprf, tmpcf, fnow[2]+1))

# ['#', '#', '#', '#']
# ['#', 'J', 'F', '#']
# ['#', 3, 2, '#']
# ['#', 4, 3, '#']

impossible = True
visited=[[0]*c for _ in range(r)]
visited[jrow][jcol]=1
jq.append((jrow, jcol, 1))

while jq:

    now=jq.pop()
    #print("nowwwwwwww", now)
    row=now[0]
    col=now[1]
    cnt=now[2]

    if row==0 or col==0 or row==r-1 or col==c-1: #가장자리에 닿으면
        impossible=False
        # print(row, col, map[row][col])
        # print(cnt)
        #answer=cnt
        print(cnt);exit()
        #if cnt<mini:mini=cnt
    else :
        for j in range(4) :

            tmprj = row+rdis[j]
            tmpcj = col+cdis[j]
            
            if 0<=tmprj<r and 0<=tmpcj<c and \
                visited[tmprj][tmpcj]==0 and\
                map[tmprj][tmpcj].isdigit() and \
                    int(map[tmprj][tmpcj])> cnt+1:
                    
                    #print("hi", tmprj, tmpcj, cnt, "map" , map[tmprj][tmpcj])
                    
                    # print()
                    visited[tmprj][tmpcj]=1 
                    jq.appendleft((tmprj, tmpcj, cnt+1))

if(impossible) : print("IMPOSSIBLE")

<반성 점>

• ㅋㅋㅋㅋㅋ 온통 나 ^^
  

<배운 점>

• 로직을 꼼꼼히 고려하기
• BFS 로 길찾기가 가능하다- 이 부분은 코드 이해 필요 추가
• dfs 로 하면 시간초과 나기 일수~ 되도록 bfs로 접근 & 해결 가능하면 bfs 로 해결 (deque)