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

# 문제 내용

- 백준 1743번: 음식물 피하기

1743번: 음식물 피하기

 

# 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

# 풀이

- 인접행렬을 사용한 dfs로 풀이

import sys

sys.setrecursionlimit(10**8)  # 재귀 제한 해제
input = sys.stdin.readline

# 가로, 세로, 쓰레기 개수
n, m, k = map(int, input().split())

# 쓰레기 위치 인접행렬
graph = [[0] * m for _ in range(n)]

# 방문 내역 표시
visited = [[False] * m for _ in range(n)]

# 정답
result = 0

# 동서남북 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

for _ in range(k):
  r, c = map(int, input().split())
  graph[r - 1][c - 1] = 1


def dfs(x, y):
  global num
  num += 1
  visited[x][y] = True

  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]

    if nx < n and ny < m and nx >= 0 and ny >= 0:
      if graph[nx][ny] == 1 and not visited[nx][ny]:
        dfs(nx, ny)


for i in range(n):
  for j in range(m):
    if graph[i][j] == 1 and not visited[i][j]:
      num = 0
      dfs(i, j)
      result = max(result, num)
print(result)