[Seop's의 코드풀이] 백준 2667 단지번호붙이기 - Python

이번에 풀어볼 문제는 백준 2667번 '단지번호붙이기'라는 문제입니다.

문제는 다음과 같습니다.

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

2667번: 단지번호붙이기

 

필자는 BFS를 활용해서 문제를 해결하고자 하였다. 

그래서 다음과 같은 방법으로 코드를 작성했다.

 

1. 모든 값이 0인 N*N 배열을 생성한다. (BFS를 수행하기 위해 내가 방문한 곳을 기록하기 위해서이다.)

2. 집이 있는 위치('1')를 따로 저장한다.( x, y 형태로 저장하여 바로 접근 할 수 있도록 한다)

3. 2번에서 저장한 값들을 토대로 주변에 마을이 있는지 체크한다. -> 4개의 방향으로 체크하고 재귀를 이용한다. 이때 BFS배열에 기록하여 지나온 곳은 검사하지 않도록 진행한다.

4. 단지별로 분류된 값을 정답 배열에 저장한 후 오름차순으로 정렬한다.

5. 정답배열의 길이와 값들을 순서대로 출력한다.

 

3번째 단계만 제대로 진행한다면 큰 어려움 없이 문제를 해결할 수 있을 것 같다.

 

전체적인 코드는 다음과 같습니다.

질문과 피드백은 언제나 감사드립니다.

 

import sys
input = sys.stdin.readline

def checkVillige(x, y) :
    dx = [-1, 1, 0,0]
    dy = [0, 0, -1, 1]
    cnt = 1
    for i in range(4):
        tx = x + dx[i]
        ty = y + dy[i]
        if tx >= 0 and tx < N and ty >= 0 and ty < N :
            if BFS[tx][ty] == 0 and villige[tx][ty] == "1" :
                BFS[tx][ty] = 1
                cnt += checkVillige(tx, ty)
    return cnt


if __name__ == "__main__":
    N = int(input())
    BFS = [[0 for i in range(N)] for j in range(N)]
    house = []
    villige = []
    for i in range(N) :
        temp = input().rstrip()
        for j in range(N) :
            if temp[j] == '1' :
                house.append([i,j])
        villige.append(temp)
    answer = 0
    ans_list = []
    for x, y in house :
        if BFS[x][y] == 0 :
            answer += checkVillige(x, y) - 1
            if answer == 0 :
                answer = 1
            ans_list.append(answer)
            answer = 0
    ans_list = sorted(ans_list)
    print(len(ans_list))
    for i in ans_list :
        print(i)