[boj] 백준 1743 음식물 피하기 python 풀이

감자156 2023. 8. 29. 10:30

문제

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

1743번: 음식물 피하기

첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다

www.acmicpc.net

문제 풀이

가장 큰 섬을 찾는 bfs 문제

코드

import sys
input = sys.stdin.readline
import collections

N, M, K = map(int, input().split())
MAP = [[0 for _ in range(M)] for _ in range(N)]
for i in range(K):
    r, c = map(int,input().split())
    MAP[r-1][c-1] = 1 # 음식물

def bfs(x,y,MAP):
    move = {(-1,0),(0,1),(1,0),(0,-1)}
    q = collections.deque()
    q.append((x,y))
    MAP[x][y] = -1 # visited

    cnt = 1
    while q:
        cx, cy = q.popleft()

        for tx, ty in move:
            nx = tx + cx
            ny = ty + cy

            if 0<=nx<N and 0<=ny<M and MAP[nx][ny] == 1:
                q.append((nx, ny))
                MAP[nx][ny] = -1
                cnt += 1

    return cnt

MAX = 0
for i in range(N):
    for j in range(M):
        if MAP[i][j] == 1:
            island_area = bfs(i,j,MAP)
            MAX = max(island_area, MAX)

print(MAX)