[python] 백준 1743 : 음식물 피하기(BFS)

[python] 백준 1743 : 음식물 피하기(BFS)

1743번: 음식물 피하기 (acmicpc.net)

1743번: 음식물 피하기

실버 1

그래프, BFS

---

접근

이차원 배열을 사용하여 그래프를 구성하고 좌표를 한칸씩 이동하면서 음식물의 크기를 계산한다.

bfs탐색이 끝나면 해당 음식물의 크기에 대한 계산이 끝난 것과 같으므로 각 bfs탐색의 반환값중 가장 큰 값을 출력하도록 한다.

 

코드

import sys; input = sys.stdin.readline
from collections import deque

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def bfs(a, b):
    queue = deque([[a, b]])
    visited[a][b] = 1
    cnt = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            ddx = x + dx[i]
            ddy = y + dy[i]
            if 0 <= ddx < N and 0 <= ddy < M:
                if not visited[ddx][ddy] and graph[ddx][ddy] == '#':
                    queue.append([ddx, ddy])
                    visited[ddx][ddy] = 1
                    cnt += 1
    return cnt

N, M, K = map(int, input().split())
visited = [[0] * (M) for _ in range(N)]
graph = [list('.' for _ in range(M)) for _ in range(N)]

max_cnt = 0
for _ in range(K):
    x, y = map(int, input().split())
    graph[x-1][y-1] = '#'

for i in range(N):
    for j in range(M):
        if graph[i][j] == '#' and visited[i][j] == 0:
            max_cnt = max(max_cnt, bfs(i, j))
print(max_cnt)

입력값으로 그래프를 구성하기 어렵기 때문에 입력한 좌표를 #으로, 나머지를 .으로 하는 이차원 배열을 하나 만들고 배열 범위 내에서 좌표를 이동하며 탐색하는 bfs 그래프를 구현했다. 반복문을 순회하며 #이 위치해있고 방문하지 않은 좌표를 bfs 탐색으로 넘기고, bfs 탐색이 종료되면 음식물 쓰래기의 크기에 대한 값을 반환한다. 마지막으로 반환값중 최대값을 출력한다.