Algorithm/백준
[백준] 음식물 피하기 (1743번) - 파이썬
potato_pizza
2024. 4. 9. 22:42
728x90
백준
음식물 피하기(1743)번
https://www.acmicpc.net/problem/1743
문제
코드
- BFS를 이용한 풀이
- 개수 세기
from collections import deque
N, M, K = map(int, input().split())
graph = [[0] * M for _ in range(N)]
visited = [[False] * M for _ in range(N)]
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
# 음식물 좌표 1 입력
for _ in range(K):
r, c = map(int, input().split())
graph[r-1][c-1] = 1
result = 0
def BFS(i, j):
queue = deque()
queue.append((i, j))
visited[i][j] = True
cnt = 1 # 시작 지점 포함하여 카운트 시작
while queue:
x, y = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < N and 0 <= ny < M:
if not visited[nx][ny] and graph[nx][ny] == 1:
visited[nx][ny] = True
cnt += 1
queue.append((nx, ny))
return cnt
for i in range(N):
for j in range(M):
if graph[i][j] == 1 and not visited[i][j]:
cnt = BFS(i, j) # BFS 함수에서 cnt를 초기화하므로 별도 초기화 불필요
result = max(result, cnt)
print(result)
728x90
반응형