문제 설명 및 링크

백준 2667번 - 단지번호붙이기

접근 방법 및 해결 전략

첫 번째

def adjacent_node(x, y): # 인접한 노드 계산하는 함수
    adjacent = []
    for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nx, ny = x + dx, y + dy
        if 0 <= nx < N and 0 <= ny < N:
            adjacent.append((nx, ny))
    return adjacent


def dfs(i, j, visited):
    count = 1
    visited[i][j] = True
    stack = []
    stack.append((i, j))
    while stack:
        x, y = stack.pop()
        adjacent = adjacent_node(x, y)
        for x, y in adjacent:
            if not visited[x][y] and map[x][y] == 1:
                visited[x][y] = True
                count += 1
                stack.append((x, y))
    return count


N = int(input())

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

visited = [[False for _ in range(N)] for _ in range(N)]

network = 0 # 단지 수
house = [] # 단지 안에 있는 집 수
for i in range(N):
    for j in range(N):
        if not visited[i][j] and map[i][j] == 1:
            network += 1
            house.append(dfs(i, j, visited))


print(network)
house = sorted(house) # 문제에서 오름차순으로 출력하라는 것 못 찾아서 헤맸음
for i in house:
    print(i)

2차원 형태로 0,1이 주어졌으므로 DFS/BFS 문제이고 둘 중 어떤 방식으로 풀어도 상관없다. 나는 DFS방식으로 풀었다.

• map는 2차원 지도이다. network는 떨어져있는 단지 수를 뜻하고, house는 단지안에 있는 집 수를 뜻한다.
• 이중 for문을 통해서 2차원 지도 전체를 확인하여 if not visited[i][j] and map[i][j] == 1 노드를 방문하지 않았고 map에서 1인 값만 통과하도록 if문으로 제한을 뒀다.
• if문을 통과해서 1인 위치를 찾았다면 단지 수를 +1 해주고 dfs함수를 실행했다. 단지 수를 +1 해준 이유는 DFS로 이어진 노드를 계속해서 찾을 수 있기 때문이다.
• dfs함수를 보면 이어진 노드를 계산하기 위해 시작 위치를 계산한 것을 포함하여 count = 1로 주었다.
• adjacent_node 함수는 해당 노드의 상하좌우로 인접한 노드를 리스트로 return한다. if 0 <= nx < N and 0 <= ny < N 통해서 map의 바깥으로 넘어가지 않도록 제한했다.
• 방문 노드를 True로 바꿔주면서 count가 1씩 증가했다.
• 마지막으로 house를 오름차순으로 출력하기 위해서 sorted 함수를 사용하여 답을 출력한다.