2667 단지번호붙이기

💡문제 분석 요약

• 정사각형 모양 지도에 0과 1이 표시되어있고, 1은 집이 있다는 의미이다. 전체 지도에서 1끼리 뭉쳐져 있는 구역이 몇개인지 세고, 각 구역별로 집 개수를 함께 알아내야한다.

💡알고리즘 설계

• 처음 생각한 건 인접한 애들끼리 쭉 따라가다가, 1인 애들끼리만 묶고 더이상 없다면 집 전체 개수 + 1 해준다. 인접한 애들이니까 BFS를 사용해야하는 게 아닌가 싶었다. 그렇게 풀다가, 사실은 모든 노드에 대해서 상하좌우를 체크하며 인접노드를 봐야하는 것을 알게 되었다. 결국 두 풀이 모두 가능했고, DFS가 조금 더 편하게 쓸 수 있으니까 DFS를 사용하였다.
• DFS를 이용해 모든 노드에 대해서 탐색한다.
• 예전에 잠깐 공부했던 경험을 살려, 상하좌우를 dx, dy 리스트로 표현하는 약간의 팁도 살려보았다.

💡코드

n = int(input())
graph = []
part_house = 0 # 각 구역별로 집 개수
all_house = [] # 전체 집 개수 list

for i in range(n): # 집 정보 초기화
    graph.append(list(map(int, input())))

# 순서대로 상, 하, 좌, 우로 이동하는 것을 의미
dx = [0, 0, 1, -1] # x축 방향 이동
dy = [1, -1, 0, 0] # y축 방향 이동

def DFS(graph, x, y):
    # 오류가 나는 상황을 정리한 것. 위, 아래로 움직이다가 x, y의 범위 밖으로 나가는 경우를 의미함.
    if x < 0 or x >= n or y < 0 or y >= n:
        return False

    if graph[x][y] == 1: # 1인 집은 탐색 대상임
        global part_house # 구역별 집 개수를 의미함
        part_house += 1
        graph[x][y] = 0 # 탐색 후, 탐색 완료의 의미로 0으로 바꿈
        for i in range(4): # 상하좌우 4개의 방향을 체크함
            nx = x + dx[i] # 기존의 좌표에 상하좌우를 더해줌
            ny = y + dy[i]
            DFS(graph, nx, ny) # 더해준 상하좌우로 다시 탐색
        return True # 모든 탐색이 완료됨
    return False # 탐색이 끝나긴 했는데 0을 만나서 끝남. 즉 1로 둘러싼 경계 밖을 간 것.

# 모든 지점에 대해서 탐색함
for i in range(n):
    for j in range(n):
        if DFS(graph, i, j) == True: # 해당 노드의 상하좌우에 집이 있다면 이라는 뜻임
            DFS(graph, i, j) # 상하좌우에 집 있으니까 방문해야지
            all_house.append(part_house) # DFS 종료 후에 얻은 구역별 집 개수를 넣어줌
            part_house = 0 # 다시 구역별로 집 체크하러 갈 땐 0으로 초기화

all_house.sort()

print(len(all_house))
for i in all_house:
    print(i)

💡시간복잡도

• N*N개의 노드에 대해 모두 탐색해야하므로 O(N^2)이 될 것 같다.

💡 틀린 이유

• 그냥 문제가 생소해서 틀렸다. 처음 접근 자체는 나름 괜찮았다. 그런데 각 구역별로 DFS를 해야하는지, 그리고 0을 만나면 어떻게 대처해야하는지 몰라서 어려웠다.
• 그리고 visited를 선언해야하는지, 아니면 기존의 graph에 0으로 덮어도 되는지 헷갈렸다. visited를 한다면 N*N을 모두 해야하는 걸로 보이는데 이것 또한 낭비가 심할 것 같아서 하진 않았다.

💡 틀린 부분 수정 or 다른 풀이

• 글에서도 썼듯이 BFS로도 풀 수 있었다. 추후 시도해본다.

💡 느낀점 or 기억할정보

• dx, dy 상하좌우 표시해서 현재의 노드 좌표에 더해주는 것 알기. nx = x + dx[i]
• 상하좌우를 어떻게 이동하는 건지 글로 쓰면서 이해해보기.