[Python] 1926번 그림

✏️ 문제

 

문제 파악

visited 2차원 배열의 값을 세 가지로 나눠서 구분했다.

• 0 → 그림이 있으나 방문하지 않은 위치
• 1 → 그림이 있고 방문한 위치
• -1 → 그림이 없어 방문할 필요 없는 위치

또한 이 문제의 경우 가로, 세로로 이동해서 방문할 수 있으니 방향 배열을 다음과 같이 구성했다.

d = [(-1, 0), (1, 0), (0, -1), (0, 1)]

 

마지막 쯤에 ValueError 뜨는 경우 그림이 하나도 없는 경우에 0이 출력되는 지 확인해보길..!

 

알고리즘

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

 

 

코드

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

for i in range(n):
  num = list(map(int, input().split()))
  for j in range(m):
    graph[i][j] = num[j]

    if num[j] == 0:
      visited[i][j] = -1

def dfs(x, y):
  stack = [(x, y)]
  visited[x][y] = 1
  area = 1

  while stack:
    x, y = stack.pop()

    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] == 0:
        stack.append((dx, dy))
        visited[dx][dy] = 1
        area += 1

  return area

for i in range(n):
  for j in range(m):
    if visited[i][j] == 0:
      areas.append(dfs(i, j))
      cnt += 1

print(cnt)
print(max(areas))

 

 

 

---

 

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

[알고리즘] DFS와 BFS