GraphTraversal05단지번호붙이기(2667)

문제

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

풀이

-처음에서부터 상하좌우로 확인을 한뒤 조건에 맞으면 카운트를 증가시키는 방법으로 진행한다.

• 너비우선 탐색 방법을 활용한다, 이용할 네 가지 방향(상,하,좌,우)를 정의한다.
• deque를 생성한다.
• while문에서 for문을 돌리면서 현재 위치에서 4가지 방향으로 위치 확인
• 각 단지 카운트 수 증가
• 총 단지 수
• 오름차순 된 단지 수

코드

import sys
sys.stdin = open("input.txt", "rt")

from collections import deque

N = int(input())
graph = []
counts = []

for _ in range(N):
  graph.append(list(map(int, input())))

# 너비 우선 탐색
def bfs(x, y):
  # 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
  dx = [-1, 1, 0, 0]  
  dy = [0, 0, -1, 1]

  # deque 생성
  queue = deque()
  queue.append((x, y))
  
  graph[x][y] = 0
  count = 1

  while queue:
    x, y = queue.popleft()
    
    # 현재 위치에서 4가지 방향으로 위치 확인
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == 1:
        graph[nx][ny] = 0
        queue.append((nx, ny))
        count += 1
  
  counts.append(count) # 각 단지 카운트 수 증가

for i in range(N):
  for j in range(N):
    if graph[i][j] == 1:
      bfs(i, j)

counts.sort()
print(len(counts)) # 총 단지수

for i in counts:
  print(i) # 오름차순 된 단지수

    

배운 것 _ 풀이2 : DFS

n = int(input())
graph = []
num = []

for i in range(n):
    graph.append(list(map(int, input())))

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def DFS(x, y):
    if x < 0 or x >= n or y < 0 or y >= n:
        return False

    if graph[x][y] == 1:
        global count
        count += 1
        graph[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            DFS(nx, ny)
        return True
    return False


count = 0
result = 0

for i in range(n):
    for j in range(n):
        if DFS(i, j) == True:
            num.append(count)
            result += 1 #아파트 단지 별 표시
            count = 0

num.sort()
print(result)
for i in range(len(num)):
    print(num[i])

그래프의 탐색 시작점을 모르기 때문에 전체를 돌면서 1인 지점에서 탐색을 시작
BFS와의 차이점은 큐 대신 재귀 사용
그 외는 위의 BFS풀이 방식대로 똑같이 진행

``