[BOJ][Python] 백준 1743번 : 음식물 피하기

- 문제 링크

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

- 풀이

가로 M, 세로 N 길이의 그래프를 만들어주고, 그래프에 음식물 쓰레기의 좌표를 넣어준다. 주의해야 할 점은, 문제에서는 배열의 시작이 (1,1)이라 자칫하면 배열의 범위를 벗어난다. 그래서 각각의 (r,c) 값을 -1씩 빼준 좌표에 음식물 쓰레기 위치 표시를 해준다. 그 뒤에 bfs를 돌리면 된다. bfs는 방문하지 않았으면서 음식물 쓰레기가 있는 위치를 잡고 돌면 된다. 

결과값을 담을 res 변수를 하나 선언해주고, bfs를 돌 때 마다 더 많은 음식물 쓰레기를 탐색한 값으로 갱신해준다.

 

 

-  코드

import sys
from collections import deque
input = sys.stdin.readline
dx = [0,0,-1,1]
dy = [-1,1,0,0]

def bfs(x, y):
    count = 1
    queue = deque()
    queue.append((x, y))
    visited[x][y] = 1

    while queue:
        a, b = queue.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if graph[nx][ny] == '#' and visited[nx][ny] == 0:
                    count += 1
                    visited[nx][ny] = 1
                    queue.append((nx, ny))
    return count

N, M, K = map(int, input().split())
graph = [[0] * M for _ in range(N)]
visited = [[0] * M for _ in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    graph[a-1][b-1] = '#' 

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

print(res)