[정올 1078] 저글링 방사능 오염

문제

승훈이는 심심한 시간에 스타크래프트(Starcraft) 게임을 하며 놀고 있었다.

스타크래프트 유닛중 하나인 저글링을 한 곳에 몰아세운 뒤, 방사능 오염 공격으로 없애보려고 했다. 

그런데 좀 더 재미있게 게임을 하기 위해서 게임을 개조하여 방사능 오염 공격을 가하면 방사능은 1초마다 이웃한 저글링에 오염된다. 

그리고 방사능에 오염된 저글링은 3초 후에 죽게 된다. 

저글링을 모아놓은 지도의 크기와 지도상에 저글링들이 놓여 있는 격자 위치가 주어질 때, 

총 몇 초 만에 저글링들을 모두 없앨 수 있는지 알아보는 프로그램을 작성하시오.

 

입력

첫째 줄은 지도의 열의 크기와 행의 크기가 주어진다. 지도는 격자 구조로 이루어져 있으며 크기는 100×100칸을 넘지 않는다.

둘째 줄부터는 지도상에 저글링들이 놓여있는 상황이 주어진다. 1은 저글링이 있는 곳의 표시이고 0은 없는 곳이다. 

마지막 줄에는 방사능오염을 가하는 위치가 열 번호 행 번호 순으로 주어진다.

 

출력

죽을 수 있는 저글링들이 모두 죽을 때까지 몇 초가 걸리는지 첫 번째 줄에 출력하고 둘째 줄에는 죽지 않고 남아 있게 되는 저글링의 수를 출력하시오.

---

접근

방사능에 오염된 저글링을 시작으로 BFS를 시작한다. 

또한 현재까지 오염된 저글링까지의 시간을 통해 최댓값 비교를 한다.

BFS가 종료되었을 때는 남아있는 저글링의 수를 카운트한다.

 

구현

- 방사능에 오염된 저글링을 입력받은 후에

- 해당 좌표를 BFS를 하는 함수에 전달한다.

M, N = map(int, input().split())
board = [list(input().strip()) for _ in range(N)]
pos = list(map(int, input().split()))
sy = pos[1] - 1
sx = pos[0] - 1

bfs(sy, sx)

- dist 리스트를 통해 오염된 저글링들이 각각 몇 초후에 오염이 되었는지 기록한다.

- 이 기록을 통해 최댓값을 구한다.

- BFS가 종료되었을 때 board에서 1을 찾아 카운트하여 남아있는 저글링을 출력한다.

def bfs(y, x):
    q = deque()
    dist = [[0 for _ in range(M)] for _ in range(N)]
    dist[y][x] = 1
    board[y][x] = '0'
    q.append((y, x))

    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    answer = 0
    while q:
        cy, cx = q.popleft()
        if dist[cy][cx] > answer:
            answer = dist[cy][cx]

        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx) and board[ny][nx] == '1':
                if dist[ny][nx] == 0:
                    board[ny][nx] = '0'
                    dist[ny][nx] = dist[cy][cx] + 1
                    q.append((ny, nx))

    count = 0
    for y in range(N):
        for x in range(M):
            if board[y][x] == '1':
                count += 1

    print(answer+2)
    print(count)
    return

---

전체 코드

import sys
from _collections import deque
input = sys.stdin.readline

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

def bfs(y, x):
    q = deque()
    dist = [[0 for _ in range(M)] for _ in range(N)]
    dist[y][x] = 1
    board[y][x] = '0'
    q.append((y, x))

    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    answer = 0
    while q:
        cy, cx = q.popleft()
        if dist[cy][cx] > answer:
            answer = dist[cy][cx]

        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx) and board[ny][nx] == '1':
                if dist[ny][nx] == 0:
                    board[ny][nx] = '0'
                    dist[ny][nx] = dist[cy][cx] + 1
                    q.append((ny, nx))

    count = 0
    for y in range(N):
        for x in range(M):
            if board[y][x] == '1':
                count += 1

    print(answer+2)
    print(count)
    return

M, N = map(int, input().split())
board = [list(input().strip()) for _ in range(N)]
pos = list(map(int, input().split()))
sy = pos[1] - 1
sx = pos[0] - 1

bfs(sy, sx)