[BFS] 상한 귤

[문제그림]

문제링크

https://www.codetree.ai/missions/2/problems/oranges-have-gone-bad?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 핵심

• 유형: BFS 유형 중 출발점이 2개 이상인 BFS
• 상한 귤(2) 가 일반 귤(1)을 상하게 한다는 점!!
  
  • 상한귤(2)을 시작점으로 bfs 시작
  • 귤이 상하면 기존에 일반 귤(1) 이 상한 귤(2)로 변경됨!
• 거의 같은 문제

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

7576번: 토마토

 

2. 코드(Python)

# 백준 - 토마토 문제와 비슷한거같음..

from collections import deque
inf = int(1e9)

n, k = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

def in_range(r, c):
    return 0 <= r < n and 0 <= c < n

# 상한 귤 찾기!
def find(board):
    starts = []
    for r in range(n):
        for c in range(n):
            if board[r][c] == 2:
                starts.append((r, c))
    return starts

# 상한 귤들을 먼저 처리
# 핵심! 귤이 상하면 1 -> 2로 변경된다!!
def bfs(starts):
    dq = deque([])
    in_queue = [[False for _ in range(n)] for _ in range(n)]
    visited = [[0 for _ in range(n)] for _ in range(n)]

    for r, c in starts:
        dq.append((r, c))
        in_queue[r][c] = True

    while dq:
        cr, cc = dq.popleft()
        for dir in range(4):
            nr = cr + dr[dir]
            nc = cc + dc[dir]
            if in_range(nr, nc) and not in_queue[nr][nc] and board[nr][nc] == 1:
                dq.append((nr, nc))
                board[nr][nc] = 2 # 귤이 상함 1 > 2
                in_queue[nr][nc] = True
                visited[nr][nc] = visited[cr][cc] + 1

    
    for r in range(n):
        for c in range(n):
            # 귤이 없었네요~
            if board[r][c] == 0:
                visited[r][c] = -1
            # 귤이 있는데(1) & 방문하지 않음(상하지않음)
            elif board[r][c] == 1 and visited[r][c] == 0:
                visited[r][c] = -2


    for row in visited:
        print(*row)

starts = find(board)
bfs(starts)