73. Python 백준 2667 단지 번호 붙이기 자세한 설명

안녕하세요 코딩하는 덕구입니다.

그래프 탐색 문제인 단지번호 붙이기 Python 백준 2667번 입니다.

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

 

먼저 최종 파이썬 2667 코드입니다.

N = int(input())
graph = []
for i in range(N):
    graph.append(list(map(int, input())))

x_dir = [1, -1, 0, 0]
y_dir = [0, 0, 1, -1]

def DFS(i, j):
    graph[i][j] = 0
    cnt = 1
    for k in range(4):
      x = i + x_dir[k]
      y = j + y_dir[k]
      if 0 <= x and x < N and 0 <= y and y < N:
        if graph[x][y] == 1:
            cnt += DFS(x, y)
    return cnt

num = 0
complexes = []
for i in range(N):
    for j in range(N):
        if graph[i][j] != 0:
            complexes.append(DFS(i, j))
            num += 1

complexes.sort()
print(num)
for c in complexes:
    print(c)

 

총 단지수와, 단지내 집의 수를 오름차순으로 하나씩 출력하는 문제입니다.

그래프의 전체 노드를 순서대로 방문합니다.

1. 만약 방문하지 않은 단지라면 총 단지 수를 1개 늘려주고,

DFS나, BFS를 이용하여 단지내 집의 개수를 찾고, 저장합니다.

2. 만약 방문했던 단지라면 방문하지 않고 다음 노드가 방문한 단지인지 확인합니다.

위의 직관을 갖고 문제를 풀어봅시다.

 

먼저 그래프를 입력 받습니다.

N = int(input())
graph = []
for i in range(N):
    graph.append(list(map(int, input())))

 

이 포스트에서는 DFS를 통해 문제를 풀게 됩니다.

현재 노드에서 탐색할 다음 노드의 좌표인 x, y값을 표현하기 위한 리스트를 작성합니다.

x_dir = [1, -1, 0, 0]
y_dir = [0, 0, 1, -1]

참고로 x, y 좌표는 이런식으로 표현할 예정입니다.

for k in range(4):
  x = i + x_dir[k]
  y = j + y_dir[k]

코드를 읽어보시면 아시겠지만.

좌표 값으로 상,하,좌,우로 움직이는 경우가 되므로

x, y에 1 혹은 -1 을 더해서 조합하는 방식입니다.

 

그래프 탐색 알고리즘인 DFS를 구현해봅시다.

재귀함수 형식으로 구현했습니다.

def DFS(i, j):
    graph[i][j] = 0
    cnt = 1
    for k in range(4):
      x = i + x_dir[k]
      y = j + y_dir[k]
      if 0 <= x and x < N and 0 <= y and y < N:
        if graph[x][y] == 1:
            cnt += DFS(x, y)
    return cnt

 

먼저 방문한 노드는 방문처리 하고 다음에 다시 방문하지 않도록 0으로 만들어 주고, 세대수를 1로 추가해 줍니다.

graph[i][j] = 0
cnt = 1

 

여기에서 DFS의 입력값은 무조건 방문하지 않은 상태에서만 호출할 것이기 때문에

위의 코드는 문제가 없습니다.

 

다음에 방문할 노드의 좌표를 만들어줍니다.

for k in range(4):
  x = i + x_dir[k]
  y = j + y_dir[k]

 

좌표가 그래프 상에서 벗어나는지 확인하고, 벗어나지 않고,

방문가능한 노드라면 방문합니다.

if 0 <= x and x < N and 0 <= y and y < N:
  if graph[x][y] == 1:
      cnt += DFS(x, y)

여기서 cnt는 단지 내 집의 개수를 저장하기 위한 변수이고,

DFS 함수는 방문한 집들의 개수를 재귀적으로 cnt에 저장하고, 리턴하게 됩니다.

if graph[x][y] == 1:
        cnt += DFS(x, y)
return cnt

 

DFS의 코드입니다.

def DFS(i, j):
    graph[i][j] = 0
    cnt = 1
    for k in range(4):
      x = i + x_dir[k]
      y = j + y_dir[k]
      if 0 <= x and x < N and 0 <= y and y < N:
        if graph[x][y] == 1:
            cnt += DFS(x, y)
    return cnt

 

단지수를 저장하기 위한 변수, 단지별 세대수를 저장하기 위한 리스트를 선언하고

그래프의 모든 노드를 하나씩 방문 가능한지 살피며

방문가능하면 DFS를 통해 방문하여, 세대수를 저장하고 단지수를 하나 늘려줍니다.

num = 0
complexes = []
for i in range(N):
    for j in range(N):
        if graph[i][j] != 0:
            complexes.append(DFS(i, j))
            num += 1

 

이후 세대수를 오름차순으로 정렬하고, 단지수, 세대수를 출력하면 됩니다.  

complexes.sort()
print(num)
for c in complexes:
    print(c)

 

단지번호 붙이기 백준 2667번 파이썬 최종 코드입니다.

N = int(input())
graph = []
for i in range(N):
    graph.append(list(map(int, input())))

x_dir = [1, -1, 0, 0]
y_dir = [0, 0, 1, -1]

def DFS(i, j):
    graph[i][j] = 0
    cnt = 1
    for k in range(4):
      x = i + x_dir[k]
      y = j + y_dir[k]
      if 0 <= x and x < N and 0 <= y and y < N:
        if graph[x][y] == 1:
            cnt += DFS(x, y)
    return cnt

num = 0
complexes = []
for i in range(N):
    for j in range(N):
        if graph[i][j] != 0:
            complexes.append(DFS(i, j))
            num += 1

complexes.sort()
print(num)
for c in complexes:
    print(c)

 

 

 단지번호 붙이기 백준 2667번 파이썬  풀이 이었습니다.

감사합니다.