[Python/백준] 4179 불!

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

4179번: 불!

<문제 해설>

너비 우선 탐색 문제이다. 배열에 있는 위치들을 다 움직인후 새로운 배열을 통해 다시 재귀함수한다.

지훈이들의 위치를 저장할 배열 J, 불들의 위치를 저장할 F 배열을 만들어 관리한다.

board에 지훈이가 지나간 위치 불들의 위치를 기록한다.

bfs를 몇번 실행했는지 기록할 count를 만들어준다. 실행될때마다 count에 1을 추가한다.

1. 문제의 주어진 값들을 다 받는다. 지훈이의 위치를 J배열에 [[y,x]]로 넣어준다. 불의 좌표는 모두 기록해 F배열에 넣어준다.
2. bfs함수를 실행한다. J배열과 F배열을 인자로 받아준다.
3. 다음 bfs에 사용할 새로운 J배열(newJ)과 F배열(newF)를 만들어준다. 
4. 우선 지훈이 부터 움직인다. 지훈이의 위치들을 저장한 배열을 읽는다. board에 현제 지훈이의 위치가 F로 바뀌었다면 전 bfs에서 불에 잠식당한거니 계산을 해주지 않는다. 아닐경우 지훈이를 상하좌우로 움직여 주면서 '.'가 있는곳으로만 움직일수 있으니 '.'가 있으면 [my,mx]를 newJ배열에 넣어주고 board[my][mx] =='J'로 바꿔서 지훈이가 이동한 곳이라는걸 기록해준다. 만약 my,mx가 board를 벋어난다면 탈출에 성공한거니 count를 출력해주고 return해준다.
5. 다음은 불이 움직인다. 불또한 상하좌우로 움직이되 #과 F인 곳으론 이동할수 없거나 이미 불이 난곳이니 이동하지 않고 아닌곳으로만 불이 번진다.
6. 만약 newJ에 아무것도 없다면 즉 지훈이가 이동할 곳이 없었다면 IMPOSSIBLE을 출력한다.
   있으면 1번으로 돌아간다.

<예시>

예시의 board를 count를 통해 보여주겠다. J는 지훈이의 위치 F는 불의 위치이다.

count = 0

처음에 받은 값을 board에 나타낸 모습이다.

count = 1

J가 이동할수 있는 곳은 아래밖에 없으니 아래로 이동한 모습이고 F는 왼쪽 아래로 번진 모습이다.

count = 2

이번에도 J는 아래로 이동했고 불은 상하좌우로 번진 모습이다. 다음 count = 3에선 J가 밖으로 나가니 3을 출력한다.

<코드>

def bfs(J,F):
    global count
    count += 1
    newJ = []
    newF = []
    for j in J:
        if board[j[0]][j[1]] != 'F':
            for m in move:
                my = m[0] + j[0]
                mx = m[1] + j[1]
                if R > my > -1 and C > mx > -1:
                    if board[my][mx] == '.':
                        newJ.append([my,mx])
                        board[my][mx] = 'J'
                else:
                    print(count)
                    return
    for f in F:
        for m in move:
            my = m[0] + f[0]
            mx = m[1] + f[1]
            if R > my > -1 and C > mx > -1:
                if board[my][mx] != '#' and board[my][mx] != 'F':
                    newF.append([my,mx])
                    board[my][mx] = 'F'

    if len(newJ) == 0:
        print('IMPOSSIBLE')
    else:
        bfs(newJ,newF)

import sys

R, C = map(int,sys.stdin.readline().split())

fire = []
board = []
move = [[1,0],[-1,0],[0,1],[0,-1]]
count = 0
for r in range(R):
    line = list(sys.stdin.readline().rstrip())
    for c in range(C):
        if line[c] == 'J':
            ji = [[r,c]]
        if line[c] == 'F':
            fire.append([r,c])
    board.append(line)

bfs(ji,fire)

<코드 설명>

def bfs(J,F): //bfs 함수 J,F가 인자로 들어간다.
    global count //몇번 진행됐는지 저장할 함수
    count += 1 //1씩 증가
    newJ = [] //새로운 지훈이의 위치
    newF = [] //새로운 불의 위치
    for j in J: //이전 지훈이들의 위치를 받아오기
        if board[j[0]][j[1]] != 'F': //이전 지훈이가 불에 잠식됐는지 잠식 안됐으면 진행
            for m in move: //상하 좌우로 움직일 좌표 생성하기
                my = m[0] + j[0]
                mx = m[1] + j[1]
                if R > my > -1 and C > mx > -1: //밖으로 나가지 않았으면
                    if board[my][mx] == '.': // '.' 일 경우 이동할수 있으니
                        newJ.append([my,mx]) //새로운 지훈이로 저장
                        board[my][mx] = 'J' //J를 표시해 이미 이동한 곳이라고 board에 저장
                else: //밖으로 나갔다면
                    print(count) //count를 출력하고
                    return //더이상 함수를 진행할 필요가 없으니 중지
    for f in F: //이전 불들의 위치 받기
        for m in move: //불을 번지게 해고
            my = m[0] + f[0]
            mx = m[1] + f[1]
            if R > my > -1 and C > mx > -1: //밖으로 나가면 에러나니 검수하고
                if board[my][mx] != '#' and board[my][mx] != 'F': //#이 아니거나 F가 아니면 이동할수 있으니
                    newF.append([my,mx]) //새로운 불의 위치를 넣어주고
                    board[my][mx] = 'F' //번졌다는걸 표시

    if len(newJ) == 0: //지훈이가 이동하지 못했으면 탈출하지도 못했다면 불가능하다는 뜻이니 출력
        print('IMPOSSIBLE')
    else:
        bfs(newJ,newF) //아닐경우 재귀함수 호출

import sys //문제가 원하는 값들 받기

R, C = map(int,sys.stdin.readline().split())

fire = []
board = []
move = [[1,0],[-1,0],[0,1],[0,-1]]
count = 0
for r in range(R):
    line = list(sys.stdin.readline().rstrip())
    for c in range(C):
        if line[c] == 'J': //지훈이는 처음에 한곳에만 있으니 이렇게 저장하고
            ji = [[r,c]]
        if line[c] == 'F': //불은 여러군데 있으니 이렇게 저장한다.
            fire.append([r,c])
    board.append(line)

bfs(ji,fire)