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

구현한 함수의 기능은 그래프를 입력받고, 좌표를 상하좌우 움직이면서 방문한 노드는 2로 값을 바꾸고, 방문해야 할 노드인 값이 1인 노드를 찾아서 반복한다. 함수는 2로 바꾼 좌표의 개수를 반환한다. 

 

그래프의 모든 노드를 돌면서 값이 1인 좌표를 함수에 넣는다. 함수가 끝나면 1과 연결된 좌표는 2로 바뀌므로 바뀐 개수를 answer에 저장하고, 다른 1을 찾는다.

<입력 >

 

N = int(input())

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

 

첫 째줄에 지도의 크기 N을 입력받고, 다음 입력에서는 이중 리스트로 그래프를 입력받는다.

<탐색>

answer = []
for x in range(N):
    for y in range(N):
        if graph[x][y] == 1:
            answer.append(search(graph, x, y, N))

 

정답을 담을 answer 리스트를 선언하고, 모든 그래프를 탐색하면서 값이 1인 좌표를 함수에 넘긴다. 함수가 끝나면 인접한 모든 1이 2로 변하고, 변한 좌표의 개수를 반환하므로, 반환된 값을 answer에 저장하고, 떨어져 있는 1의 좌표를 찾아서 반복한다.

<함수>

def search(graph, x, y, N):
    # 상, 하, 좌, 우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue = [[x, y]]
    visit = 1
    graph[x][y] = 2

    while queue:
        current_x, current_y = queue.pop()
        for i in range(4):
            new_x = current_x+dx[i]
            new_y = current_y+dy[i]

            if 0 <= new_x < N and 0 <= new_y < N and graph[new_x][new_y] == 1:
                graph[new_x][new_y] = 2
                visit += 1
                queue.append([new_x, new_y])
    return visit

 

좌표 상, 하, 좌, 우를 바꾸기 위해서 dx와 dy를 만든다. queue에는 처음 좌표의 값을 넣고, visit에는 처음 좌표가 있으므로 1로 시작한다. 처음 지점인 graph [x][y]를 2로 만든다.

 

queue가 있는 동안 while문을 반복한다.

현재 좌표를 queue에서 받아와서 해당 좌표를 기준으로 상, 하, 좌, 우를 탐색한다. 주변 노드가 1인 경우 해당 좌표의 값을 2로 바꾸고, visit의 값을 1 증가시키고, 좌표 값을 queue에 넣는다.

 

반복이 끝나면 방문한 좌표의 개수인 visit를 반환한다.

<출력>

 

answer.sort()
print(len(answer))
for i in answer:
    print(i)

 

오름차순으로 값을 출력해야 하므로 answer을 정렬해주고, 총개수인 answer의 길이와, answer의 값을 차례대로 출력한다.

 

<전체 코드>

def search(graph, x, y, N):
    # 상, 하, 좌, 우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue = [[x, y]]
    visit = 1
    graph[x][y] = 2

    while queue:
        current_x, current_y = queue.pop()
        for i in range(4):
            new_x = current_x+dx[i]
            new_y = current_y+dy[i]

            if 0 <= new_x < N and 0 <= new_y < N and graph[new_x][new_y] == 1:
                graph[new_x][new_y] = 2
                visit += 1
                queue.append([new_x, new_y])
    return visit


N = int(input())

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

answer = []
for x in range(N):
    for y in range(N):
        if graph[x][y] == 1:
            answer.append(search(graph, x, y, N))

answer.sort()
print(len(answer))
for i in answer:
    print(i)