[boj] 단지 번호 붙이기_2667

그래프를 순회하는 대표적인 문제라고 생각한다.

 

격자(테이블) 형태의 그래프를 위 아래로 탐색해가며 같은 군집(?)을 결정하는 문제이다.

 

이 문제 또한 나동빈 저자의 '이것이 코딩 테스트다' 책의 예제 코드를 이용하였다.

 

dfs 알고리즘을 통해 이어진 노드를 탐색하고 그 개수만큼을 리스트에 담아 출력하는 문제이다.

 

여담이지만, 효율적인 코딩테스트 공부를 위해 이렇게 책의 코드를 적극적으로 활용해 시간을 절약하는 좋은 것인지...아니면 나름대로의 고민을 하며 인고의 시간을 보내는 것이 좋은 것인지는 잘 모르겠다...

# 단지번호 붙이기

N = int(input())

graph = []
list_num = []
count = 0

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

def dfs(x, y):
    global count
    if x <= -1 or y <= -1 or x >= N or y >= N:
        return False
    if graph[x][y] == 1:
        count += 1
        graph[x][y] = 0
        dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y+1)
        dfs(x, y-1)
        return True
    return False

result_group = 0

for i in range(N):
    for j in range(N):
        if dfs(i, j) == True:
            result_group += 1
            list_num.append(count)
            count = 0

list_num.sort()
print(result_group)
for i in list_num:
    print(i)

 

※ 해당 게시물은 개인 코딩 공부를 위해 작성하는 글입니다. 문제가 있을 경우 dusrlf2003@naver.com으로 연락주세요!