[Python] 2667번 단지번호 붙이기

✏️ 문제

 

문제 파악

집이 모여있는 곳을 모두 접근해야 하므로 깊이 우선 탐색을 사용해서 풀었다.

그리고 단지 개수를 세야 하므로 깊이 우선 탐색을 돌 때마다 개수를 +1 해주었고 깊이 우선 탐색에 단지 번호를 매개 변수로 주어 풀었다.

 

여기서 나는 visited 2차원 배열에 조건을 주었는데

• 0 → 방문 안해도 되는 거
• 1 → 방문한 거
• -1 → 방문해야 되는데 아직 방문 안한 거

이렇게 세 가지로 나눠서 조건문을 구분하였다.

 

예제를 넣었을 때는 잘 풀렸는데 틀렸다고 나온다면 각 단지내 집의 수를 단지 번호 차례대로가 아닌 각 단지내 집의 수를 오름차순으로 출력했는지 확인해보아야 한다! (내 얘기)

 

알고리즘

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

 

 

코드

n = int(input())

d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
graph = [[0] * (n+1) for _ in range(n+1)]
visited = [[0] * (n+1) for _ in range(n+1)]
cnt = 0
res = []

for i in range(1, n+1):
  s = input()
  for j in range(1, n+1):
    graph[i][j] = int(s[j-1])

    if int(s[j-1]) == 1:
      visited[i][j] = -1
  
def dfs(x, y, num):
  visited[x][y] = num

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

    if 0 < nx <= n and 0 < ny <= n and graph[nx][ny] == 1 and visited[nx][ny] == -1: 
      dfs(nx, ny, num) 

for x in range(1, n+1):
  for y in range(1, n+1):
    if visited[x][y] == -1:
      cnt += 1
      dfs(x, y, cnt)

for i in range(1, cnt+1):
  res.append(sum(row.count(i) for row in visited))
res.sort()

print(cnt)
for i in range(len(res)):
  print(res[i])

 

 

 

---

 

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

[알고리즘] DFS와 BFS