[파이썬] 백준 2667번 단지번호붙이기 - DFS 방식 문제 풀이

단지 번호 붙이기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	52272	20533	13197	37.982%

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선 상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1	예제 출럭 1
7 0110100 0110101 1110101 0000111 0100000 0111110 0111000	3 7 8 9

소스코드

from sys import stdin
n = int(input())
# 데이터 저장용 공간 matrix
matrix = [[0]*n for _ in range(n)]
# 방문 내역 저장용 visited
visited = [[0]*n for _ in range(n)]

# matrix에 아파트 유무 0과 1 저장
for i in range(n):
    line = stdin.readline().strip()
    for j, b in enumerate(line):
        matrix[i][j] = int(b)

# 방향 확인용 좌표 dx와 dy
# 중앙을 기준으로 좌/우/위/아래
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

# DFS 함수 정의
def dfs(x, y, c):
    visited[x][y] = 1   # 방문 여부 표시
    global nums            # 아파트 단지 수를 세기위한 변수
    # 아파트가 있으면 숫자를 세어줍니다.
    if matrix[x][y] == 1:
        #matrix[x][y] = c # 아파트 단지별 숫자 표시용
        nums += 1
    # 해당 위치에서 좌/우/위/아래 방향의 좌표를 확인해서 dfs 적용
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if visited[nx][ny] == 0 and matrix[nx][ny] == 1:
                dfs(nx,ny, c)

cnt = 1 # 아파트 단지 세기 위한
numlist = [] # 아파트 단지별 숫자
nums=0 # 아파트 수
for a in range(n):
    for b in range(n):
        if matrix[a][b] == 1 and visited[a][b] == 0:
            dfs(a,b,cnt)
            numlist.append(nums)
            nums = 0
#            cnt += 1 # 아파트 단지 별 표시용

print(len(numlist))
for n in sorted(numlist):
    print(n)

• 결과

  • 메모리 : 29372 KB
  • 시간 : 56 ms

• 문제 풀이

  • 기본으로 주어진 아파트 맵을 matrix에 표시합니다.

  • 방문 여부를 확인하기 위한 visited를 matrix와 똑같은 모양으로 만들었습니다.

  • matrix에 아파트가 있는 위치를 입력받아서 표시하도록 하였습니다.

  • 

    matrix와 visited의 좌표 모습

     

  •  좌표를 설정한 후 DFS 함수를 적용해서 아파트 단지를 하나씩 찾아나갑니다.
  •  좌표를 하나씩 찾아나가는 모습입니다. 2단지 아파트를 찾아서 2로 하나씩 바꾸어 나가는 모습입니다.

  • 

    아파트 2단지

     

  • 아파트를 단지별로 모두 구분한 후의 결과

    

    최종 단지 구분 결과물

  • 전체 맵에 대해서 아파트를 찾아야 하므로 이중 for문을 사용해서 각 좌표를 찾아나갑니다. 해당 좌표에 아파트가 있을 경우 dfs를 적용해서 아파트를 찾아 나가도록 합니다.

  • 방문 경로를 연속해서 도는 동알 해당 경로에 이어지는 아파트들을 모두 찾으며 숫자를 세어나갑니다.

  • 해당 결과는 확인하지 않아도 되지만 시각적으로 보기 위해서 코드 몇 줄을 추가한 것입니다.
  • 아파트 단지를 바꿔나가는 동안 nums를 통해서 아파트 수를 세어나간 후 numlist에 저장해줍니다.
  • 마지막에 정렬시킨 후 최종적으로 출력하면 결과를 확인할 수 있습니다.

• 유사한 문제

  • 2020/03/07 - [파이썬/알고리즘] - [파이썬] 백준 2606번 바이러스 - BFS방식과 DFS 방식 비교

  • 2020/03/07 - [파이썬/알고리즘] - [파이썬] 백준 1260번 DFS와 BFS

  • 2020/03/06 - [파이썬/알고리즘] - [Python] 백준 1654번 랜선 자르기 - 이분 탐색

• 문제 출처

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