[Python] 백준 풀기 2667 - 단지번호붙이기

파이썬 백준 2667번

실버1

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

2667번: 단지번호붙이기

 

 

 

 

 

문제 보기

분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

 

 

 

 

문제 풀기

그래프 탐색을 하는 문제이다. 연습을 위해 DFS 방법으로 접근을 하였다.

 

 

주어진 예제 입력에 따라 2차원 리스트로 집의 위치를 모두 town_map_input 에 입력받는다.

    town_map_input = [list(map(str, inputdata().split())) for _ in range(N)]

 

지금 보니 뻘짓을 한 부분이 있는데 입력을 str 으로 받아 쓸데없는 코드 줄이 추가되었다.

다음엔 int 로 받아야겠다.

str 으로 받은 문자열을 각각 리스트 하나씩 분리 저장하기 위하여 아래의 코드가 사용되었다.;;

    for i in range(N):
        town_sum = []
        for town in town_map_input[i]:
            town_sum += town
        # print(town_sum)            # test print
        town_map.append(town_sum)

 

그리고, 단지 번호를 카운트하고 저장할 town_count = 0 를 지정해 주고, 각 단지별로 집의 개수를 저장할 house_count_ls = [] 도 지정해 준다.

    town_count = 0
    house_count_ls = []

 

N 개의 정사각형 행렬이기에 for loop 을 N 번 두 번 돌려 만약 단지에 첫 집이 있는 town_map[i][j] == '1' 을 만족할 때 단지의 수 town_count 를 +1 해주고 그 집을 빈칸 ' ' 처리해준다. 그리고 단지의 시작이기에 house_count 를 1 로 세어주면서 동시에 초기화시킨다. 이제 fn(DFS) 로 재귀 함수에 진입한다.

    for i in range(N):
        for j in range(N):
            if town_map[i][j] == '1':
                town_count += 1
                town_map[i][j] = ' '
                house_count = 1
                fnDFS(N, i, j)

 

현재 위치의 집 좌표에서 왼쪽, 오른쪽, 아래, 위에 대해 모든 탐색을 준비하고 마을 외부로 나가지 않는 범위 if (0 <= nx < N) and (0 <= ny < N): 에서 집이 있는지 if town_map[nx][ny] == '1': 확인하고 빈칸 표시 및 집의 개수를 카운트한다. 이 작업이 끝나면 fnDFS 로 지속적인 탐색을 한다.

def fnDFS(N, x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if (0 <= nx < N) and (0 <= ny < N):
            if town_map[nx][ny] == '1':
                town_map[nx][ny] = ' '
                global house_count
                house_count += 1
                fnDFS(N, nx, ny) 

 

글로벌 변수로 지정된 global house_count 는 1로 초기화되기 전까지 누적되고 최종 fnDFS 함수를 빠져나오는 순간 house_count_ls 에 순차적 저장된다.

                house_count_ls.append(house_count)

 

최종적으로 누적된 전체 단지의 수 town_count 를 출력하고 house_count 는 오름차순 출력을 위해 house_count_ls.sort() 로 순서 정렬 후 출력한다.

    print(town_count)
    house_count_ls.sort()
    for h in house_count_ls:
        print(h)

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

def fnDFS(N, x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if (0 <= nx < N) and (0 <= ny < N):
            if town_map[nx][ny] == '1':
                town_map[nx][ny] = ' '
                global house_count
                house_count += 1
                fnDFS(N, nx, ny)                


if __name__ == "__main__":
    N = int(inputdata().strip())
    town_map_input = [list(map(str, inputdata().split())) for _ in range(N)]
    # print(town_map_input)            # test print
    town_map = []
    for i in range(N):
        town_sum = []
        for town in town_map_input[i]:
            town_sum += town
        # print(town_sum)            # test print
        town_map.append(town_sum)
    # print(town_map)            # test print
    
    town_count = 0
    house_count_ls = []
    for i in range(N):
        for j in range(N):
            if town_map[i][j] == '1':
                town_count += 1
                town_map[i][j] = ' '
                house_count = 1
                fnDFS(N, i, j)
                house_count_ls.append(house_count)
                # print(house_count_ls)
    # print(town_map)            # test print
    print(town_count)
    # print(house_count_ls)            # test print

    house_count_ls.sort()
    for h in house_count_ls:
        print(h)

 

 

 

 

 

추가 하기

시각적 이해를 위해 그래프 모양을 출력해 보았다.

import sys
inputdata = sys.stdin.readline

def fnDFS(N, x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if (0 <= nx < N) and (0 <= ny < N):
            if town_map[nx][ny] == '1':
                town_map[nx][ny] = ' '
                global house_count
                house_count += 1
                fnDFS(N, nx, ny)                


if __name__ == "__main__":
    N = int(inputdata().strip())
    town_map_input = [list(map(str, inputdata().split())) for _ in range(N)]
    print(town_map_input)            # test print
    town_map = []
    for i in range(N):
        town_sum = []
        for town in town_map_input[i]:
            town_sum += town
        # print(town_sum)            # test print
        town_map.append(town_sum)
    print(town_map)            # test print
    
    town_count = 0
    house_count_ls = []
    for i in range(N):
        for j in range(N):
            if town_map[i][j] == '1':
                town_count += 1
                town_map[i][j] = ' '
                house_count = 1
                fnDFS(N, i, j)
                house_count_ls.append(house_count)
                # print(house_count_ls)
    print(town_map)            # test print
    print(town_count)
    # print(house_count_ls)            # test print

    house_count_ls.sort()
    for h in house_count_ls:
        print(h)



# 7
# 1110101
# 0110101
# 1110101
# 0000111
# 0100000
# 0111110
# 0111001


# [['1110101'], ['0110101'], ['1110101'], ['0000111'], ['0100000'], ['0111110'], ['0111001']]

# [
#     ['1', '1', '1', '0', '1', '0', '1'], 
#     ['0', '1', '1', '0', '1', '0', '1'], 
#     ['1', '1', '1', '0', '1', '0', '1'], 
#     ['0', '0', '0', '0', '1', '1', '1'], 
#     ['0', '1', '0', '0', '0', '0', '0'], 
#     ['0', '1', '1', '1', '1', '1', '0'], 
#     ['0', '1', '1', '1', '0', '0', '1']
# ]

# [
#     [' ', ' ', ' ', '0', ' ', '0', ' '], 
#     ['0', ' ', ' ', '0', ' ', '0', ' '], 
#     [' ', ' ', ' ', '0', ' ', '0', ' '], 
#     ['0', '0', '0', '0', ' ', ' ', ' '], 
#     ['0', ' ', '0', '0', '0', '0', '0'], 
#     ['0', ' ', ' ', ' ', ' ', ' ', '0'], 
#     ['0', ' ', ' ', ' ', '0', '0', ' ']
# ]


# 4
# 1
# 8
# 9
# 9