백준 2667번 <단지번호붙이기>

백준 알고리즘 2667번

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

---

2667번

입력으로 첫 줄에 지도의 크기 N이 들어오고 그 다음 N줄에 각각 N개의 자료가 들어온다.

 

출력으로 첫 줄에는 총 단지 수가 출력되고 그 다음 줄부터 각 단지 내의 집 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하면 된다.

---

문제 해결

어떻게 풀어야 할지! 그리고 그 방법을 어떻게 이해해야 할지! 엄청 오래 걸렸다....

 

DFS를 사용해서 해결했다.

입력으로 들어오는 지도 데이터를 data로 입력받아서 DFS를 할 때 사용하는 방문처리 리스트로 사용하였다.

(0은 방문한 곳, 1은 방문하지 않은 곳.)

 

1. data의 각 좌표들을 다 dfs함수로 검사한다.

2. dfs함수의 반환 값이 0이면 continue.

3. 그렇지 않으면 answer에 append한다.

 

dfs(x, y, n, data) 함수

- data는 입력으로 들어온 지도 데이터, n은 지도의 크기, x와 y는 data의 좌표를 의미한다.

1. result를 0으로 초기화한다.

2. x와 y 중 하나라도 범위를 넘어간다면 result를 반환

3-1. data[x][y]가 '1'이라면 data[x][y]를 '0'으로 바꾸고 result에 1을 더한다.

3-2. 상하좌우를 인자로 dfs 함수를 호출한다. 그 결과를 result에 더한다. 

4. result를 반환

 

이렇게 하면 1로 연결된 부분을 상하좌우로 타고 가서 개수를 셀 수 있고 dfs 함수는 그 개수를 반환해준다.

(방문한 곳은 0으로 표시되거나 아파트가 없는 곳은 0이기 때문에 1로 연결된 부분만 카운트하고 함수가 끝난다.)

---

코드

def main():
    n = int(input())
    data = [[] for i in range(n)]

    for i in range(n):
        temp = list(input())
        data[i] = temp
    answer = []
    for i in range(n):
        for j in range(n):
            temp = dfs(i, j, n, data)
            if temp == 0:
                continue
            else:
                answer.append(temp)
    print(len(answer))
    answer.sort()
    for i in answer:
        print(i)

def dfs(x, y, n, data):
    result = 0
    if x < 0 or y < 0 or x >= n or y >= n:
        return result
    if data[x][y] == '1':
        data[x][y] = '0'
        result += 1
        result += dfs(x - 1, y, n, data)
        result += dfs(x + 1, y, n, data)
        result += dfs(x, y - 1, n, data)
        result += dfs(x, y + 1, n, data)
    return result

main()

---

결과

출력형식 안 맞춰서 한번 틀린 건 안 비밀..

---