[백준 4179번] 불!

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

4179번: 불!

이 문제는 BFS를 해줄 것이 2가지입니다.

하나는 불이 퍼지는 것.

또 하나는 지훈이의 이동.

이 문제가 조금 애매하게 서술해서

어떤 걸 먼저 BFS해줘야할지 애매해서 질문글을 찾아보니

불을 먼저 BFS해주는 걸로 했습니다.

#1. 불이 먼저 번짐
new_fire=deque()
for x,y in fire:
    for d in range(4):
        nx=x+dx[d]
        ny=y+dy[d]

        if nx<0 or nx>=N or ny<0 or ny>=M:
            continue

        if room[nx][ny]==5:
            continue
        if room[nx][ny]==2:
            continue
        if f_visited[nx][ny]==True:
            continue

        new_fire.append([nx,ny])
        room[nx][ny]=2
        f_visited[nx][ny]=True


fire=new_fire

 

불이 번지는 걸 구현한 코드입니다.

현재 fire라는 queue의 상하좌우를 기준으로

불을 계속 번지게 만들었습니다.

#2. 지훈이가 움직임
new_jihon=deque()
while jihon:
    x,y=jihon.popleft()
    if (x == 0 or x == N - 1) and 0 <= y < M:
        out = True
        answer=visited[x][y]
        break

    elif 1<=x<N-1 and (y==0 or y==M-1):
        out=True
        answer=visited[x][y]
        break

    for d in range(4):
        nx=x+dx[d]
        ny=y+dy[d]

        if nx<0 or nx>=N or ny<0 or ny>=M:
            continue

        if room[nx][ny]==5:
            continue
        if room[nx][ny]==1:
            continue
        if room[nx][ny]==2:
            continue

        if visited[nx][ny]:
            continue
        visited[nx][ny]=visited[x][y]+1
        room[nx][ny]=1
        new_jihon.append([nx,ny])
    room[x][y]=0
jihon=new_jihon
if out==True:
    break

if not jihon:
    break

그 다음에는 지훈이가 움직이는 것을 구현했습니다.

지훈이는 이동할 때

최솟값을 구해야하므로

visited값을 계속 하나씩 올려주는 걸로 구현했습니다.

 

#백준 4179번 불!
from collections import deque


N,M=map(int,input().split())
room=[]
j_x=0
j_y=0
fire=deque()
f_visited=[[False]*M for _ in range(N)]

for i in range(N):
    data=list(input().rstrip())

    for j in range(M):
        if data[j]=='.':
            data[j]=0
        if data[j]=='J':
            j_x=i
            j_y=j
            data[j]=1
        if data[j]=='F':
            data[j]=2
            fire.append([i,j])
            f_visited[i][j]=True
        if data[j]=='#':
            data[j]=5
    room.append(data)


jihon=deque()
jihon.append([j_x,j_y])

dx=[0,0,1,-1]
dy=[1,-1,0,0]
visited=[[0]*M for _ in range(N)]
visited[j_x][j_y]=1

out=False
answer=0

while True:
    #1. 불이 먼저 번짐
    new_fire=deque()
    for x,y in fire:
        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=N or ny<0 or ny>=M:
                continue

            if room[nx][ny]==5:
                continue
            if room[nx][ny]==2:
                continue
            if f_visited[nx][ny]==True:
                continue

            new_fire.append([nx,ny])
            room[nx][ny]=2
            f_visited[nx][ny]=True


    fire=new_fire
    #2. 지훈이가 움직임
    new_jihon=deque()
    while jihon:
        x,y=jihon.popleft()
        if (x == 0 or x == N - 1) and 0 <= y < M:
            out = True
            answer=visited[x][y]
            break

        elif 1<=x<N-1 and (y==0 or y==M-1):
            out=True
            answer=visited[x][y]
            break

        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=N or ny<0 or ny>=M:
                continue

            if room[nx][ny]==5:
                continue
            if room[nx][ny]==1:
                continue
            if room[nx][ny]==2:
                continue

            if visited[nx][ny]:
                continue
            visited[nx][ny]=visited[x][y]+1
            room[nx][ny]=1
            new_jihon.append([nx,ny])
        room[x][y]=0
    jihon=new_jihon
    if out==True:
        break

    if not jihon:
        break


if answer>0:
    print(answer)
else:
    print("IMPOSSIBLE")

전체 코드입니다.

반복문을 계속 돌려서

jihon의 큐가 없다-->불 타 죽었으므로 반복끝냄

나갔다-->나갔으므로 반복문 끝냄.

이렇게 구현했습니다.

#백준 4179번 불!
from collections import deque


N,M=map(int,input().split())
room=[]
j_x=0
j_y=0
fire=deque()

for i in range(N):
    data=list(input().rstrip())

    for j in range(M):
        if data[j]=='.':
            data[j]=0
        if data[j]=='J':
            j_x=i
            j_y=j
            data[j]=1
        if data[j]=='F':
            data[j]=2
            fire.append([i,j])
        if data[j]=='#':
            data[j]=5
    room.append(data)


jihon=deque()
jihon.append([j_x,j_y])

dx=[0,0,1,-1]
dy=[1,-1,0,0]
visited=[[-1]*M for _ in range(N)]
visited[j_x][j_y]=0

out=False
answer=0

while True:
    #1. 불이 먼저 번짐
    new_fire=deque()
    for x,y in fire:
        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=N or ny<0 or ny>=M:
                continue

            if room[nx][ny]==5:
                continue
            if room[nx][ny]==2:
                continue
            new_fire.append([nx,ny])
            room[nx][ny]=2


    fire=new_fire
    #2. 지훈이가 움직임
    new_jihon=deque()
    while jihon:
        x,y=jihon.popleft()
        if (x == 0 or x == N - 1) and 0 <= y < M:
            out = True
            answer=visited[x][y]
            break

        elif 1<=x<N-1 and (y==0 or y==M-1):
            out=True
            answer=visited[x][y]
            break

        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=N or ny<0 or ny>=M:
                continue

            if room[nx][ny]==5:
                continue
            if room[nx][ny]==1:
                continue
            if room[nx][ny]==2:
                continue

            if not visited[nx][ny]==-1:
                continue
            visited[nx][ny]=visited[x][y]+1
            room[nx][ny]=1
            new_jihon.append([nx,ny])
        room[x][y]=0
    jihon=new_jihon
    if out==True:
        break

    if not jihon:
        break


if answer>0:
    print(answer+1)
else:
    print("IMPOSSIBLE")

 

위랑 로직은 같지만

이 코드는 100%에서 틀렸습니다가 떴습니다.

처음에 무척이나 황당했습니다.

구글링해서 코드를 고치고 다른 방식으로 풀어도

100%에서 틀렸다고 뜨길래

이게 뭐지 하고 샷건 치다가...

visted를 -1로 초기화한 걸

0으로 초기화했습니다.

당연히 출력할 때 answer에 1 더하는 것도 생략

그랬더니 100%에서 통과하더군요.

흠...이게 과연 큰 차이인가 싶긴 하지만...

앞으로는 이런 식으로 초기화를 하면 좋겠다 생각도 들었습니다.

 

#백준 4179번 불!
from collections import deque


N,M=map(int,input().split())
room=[]
j_x=0
j_y=0
fire=deque()
f_visited=[[0]*M for _ in range(N)]

for i in range(N):
    data=list(input().rstrip())

    for j in range(M):
        if data[j]=='.':
            data[j]=0
        if data[j]=='J':
            j_x=i
            j_y=j
            data[j]=1
        if data[j]=='F':
            data[j]=2
            fire.append([i,j])
            f_visited[i][j]=1
        if data[j]=='#':
            data[j]=5
    room.append(data)


jihon=deque()
jihon.append([j_x,j_y])

dx=[0,0,1,-1]
dy=[1,-1,0,0]
visited=[[0]*M for _ in range(N)]
visited[j_x][j_y]=1

out=False
answer=0

def bfs():
    #1. 불이 먼저 번짐
    while fire:
        x,y=fire.popleft()
        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=N or ny<0 or ny>=M:
                continue

            if room[nx][ny]==5:
                continue
            if f_visited[nx][ny]:
                continue
            fire.append([nx,ny])
            f_visited[nx][ny]=f_visited[x][y]+1

    #2. 지훈이가 움직임
    while jihon:
        x,y=jihon.popleft()

        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]
            if 0<=nx<N and 0<=ny<M:
                if not room[nx][ny]==5 and not visited[nx][ny]:
                    if visited[x][y]+1<f_visited[nx][ny] or not f_visited[nx][ny]:
                        visited[nx][ny]=visited[x][y]+1
                        jihon.append([nx,ny])

            else:
                return visited[x][y]


    if not jihon:
        return 0

answer=bfs()
if answer>0:
    print(answer)
else:
    print("IMPOSSIBLE")

 

https://seongonion.tistory.com/87

[백준] 4179번 불! - 파이썬(Python)

이건 구글링해서 구현한 코드.

이 코드는 처음에

불을 bfs해주면서

불이 갈 수 있는 모든 경로를 표시합니다.

그리고 지훈이 움직이는 경로에서,

지훈이 움직이는 시간<불이 이동한 시간이라면 움직이게 해줍니다.

만약 지훈>=불이라면

불이 먼저 그 지점에 있는 것이므로

지훈이가 그 지점을 이동하면 불타 죽는다는 말이 됩니다.

이 방식이 시간을 더욱 더 세이브해주는 방식이라서

공부거리가 상당히 많이 되었습니다.