[Python] 1743번 음식물 피하기

✏️ 문제

 

문제 파악

이번 문제에서는 방문할 필요가 없는 위치가 아니라 방문해야 하는 위치만 알려주므로 이를 잘 알고 코드를 짜야한다.

나는 다음과 같이 visited 배열을 줬다. 

• 1 → 음식물이 있지만 방문하지 않은 위치
• 2 → 음식물이 있어 이미 방문한 위치

이를 바탕으로 다음 위치를 방문할 때 다음 위치가 음식물이 있지만 방문하지 않은 위치인 지(if visited[위치] == 1) 조건문을 주어 풀었다.

 

알고리즘

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

 

 

코드

from collections import deque

n, m, k = map(int, input().split())
graph = [[0] * m for _ in range(n)]
visited = [[0] * m for _ in range(n)]
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
size = []

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

def bfs(x, y):
  q = deque([(x, y)])
  visited[x][y] = 2
  size = 0

  while q:
    x, y = q.popleft()
    size += 1

    for i in range(4):
      dx = x + d[i][0]
      dy = y + d[i][1]

      if 0 <= dx < n and 0 <= dy < m and visited[dx][dy] == 1 and graph[dx][dy] == 1:
        q.append((dx, dy))
        visited[dx][dy] = 2

  return size

for i in range(n):
  for j in range(m):
    if visited[i][j] == 1:
      size.append(bfs(i, j))

print(max(size))

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS