[파이썬] 백준 2667 : 단지번호 붙이기 (실버1)

[파이썬] 백준 2667 : 단지번호 붙이기 (실버1)

2667번: 단지번호붙이기

---

문제

---

풀이

0. 방향성 생각

2차원 배열의 탐색이고 군집의 크기와 개수를 탐색하는 문제이다.

주어진 배열의 길이가 충분히 짧아서 DFS로도 나쁘지 않은 성능을 낼 수 있을 것 같다.

 

1. 입력 받기

import sys
sys.setrecursionlimit(10**6)

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

배열의 크기가 충분히 작아서 제한을 늘릴 필요는 없지만 혹시 모르니까 DFS 탐색 문제에서는 제한을 올려준다.

NxN 정사각형 array이다.

문자열로 들어오기 때문에 한 원소에 접근할 수 있게 리스트로 바꿔준다.

 

2. DFS 함수 정의

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

group,table = 1,{}
for i in range(N):
    for j in range(N):
        if apt[i][j] == '1':
            table[group] = dfs(i,j)
            group += 1

주어진 위치에 아파트가 있을 (값이 '1'인 경우) 경우 DFS함수를 호출해 연결된 모든 단지를 탐색한다.

그림처럼 단지 이름과 개수를 매칭 시킬 필요는 없지만 그렇게 하기 위해 group, table 딕셔너리를 만들어준다.

for문을 돌리면서 값에 접근할 때 DFS를 호출할 수 있으면 딕셔너리에 단지 : 아파트 수를 매칭시킨다.

카운트 할 때 마다 단지명을 바꾸기 위해 group을 추가해준다.

리스트에 바로 넣고 카운팅만 해줘도 같은 결과를 얻을 수 있다.

print(table)
{1: 7, 2: 8, 3: 9}

이런식으로 단지 : 아파트수가 딕셔너리에 저장된다.

 

3. 결과 출력

answer = list(table.values())
answer.sort()

print(group-1)
print(*answer)

리스트의 values만 가져와서 리스트로 만들어주고 정렬한다.

group은 마지막 단지를 셀 때 한 번 더 카운팅 돼었으므로 1을 빼준다.

단지 수는 언패킹을 통해서 한 번에 출력한다.

---

전체 코드

import sys
sys.setrecursionlimit(10**6)

N = int(sys.stdin.raedline())
apt = []
for i in range(N):
    s = list(sys.stdin.raedline())
    apt.append(s)
    
def dfs(x,y):
    if x<0 or x>=N or y<0 or y>=N :
        return 0
    if apt[x][y] == '1' :
        apt[x][y] = '0'
        return 1+dfs(x-1,y)+dfs(x+1,y)+dfs(x,y-1)+dfs(x,y+1)
    return 0

group,table = 1,{}
for i in range(N):
    for j in range(N):
        if apt[i][j] == '1':
            table[group] = dfs(i,j)
            group += 1

answer = list(table.values())
answer.sort()

print(group-1)
print(*answer)