[BOJ] 백준 2667 단지번호 붙이기 python

문제

2667번: 단지번호붙이기

---

 

풀이

지도의 크기와 정사각형 모양의 지도를 입력으로 받아서 이를 통해서 아파트 단지의 개수와 단지 내의 아파트의 수를 찾는 문제이다. 지도를 입력 받아서 이를 2차원 리스트에 저장한다. 그리고 이 리스트를 2중 for문을 돌려서 아파트가 있는 지점을 찾는다. 이때 찾아낸 지점에서 dfs를 돌린다.

여기에서 dfs를 실행하면 이 좌표를 기준으로 상하좌우의 값을 확인하여 아파트가 위치하고 있는지 확인한다. 만약 아파트가 위치하고 있으면 해당 위치의 값을 1이 아닌 다른 값으로 바꾸고, 해당 위치로 이동하여 dfs를 실행한다. 값을 바꾸는 이유는 확인된 좌표이기 때문이다. 만약 값을 바꾸지 않게 되면 단지의 수가 아파트의 수와 같게 나오게 된다.

dfs가 다 돌아지면 단지수를 증가한다. 그리고 이 과정을 반복하여 원하는 값을 찾아낸다.

---

 

코드

def dfs(x, y):
    global cnt
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    for i in range(4):                          # 상하좌우의 방향을 확인
        mx, my = x + dx[i], y + dy[i]
        if 0 <= mx < N and 0 <= my < N:         # 범위를 벗어나지 않으면
            if graph[mx][my] == 1:              # 주변에 아파트가 있으면?
                cnt += 1
                graph[mx][my] = 0               # 확인한 아파트인데 나중에 이 위치에서 dfs가 돌아가면 안되서 값 변경
                dfs(mx, my)
    return cnt

N = int(input())
graph = [list(map(int, input().strip())) for _ in range(N)]
res = 0
dfsRes = 0
apartNum = []

for x in range(N):                              # 그래프의 y축 이동
    for y in range(N):                          # 그래프의 x축 이동
        if graph[x][y] == 1:                    # 만약 해당 위치에 아파트가 있다면?
            cnt = 0
            dfsRes = dfs(x, y)
            if dfsRes == 0:                     # 이 코드에서는 단지내의 아파트가 1개만 존재하는 경우에는 값을 0을 리턴하기 때문에 직접 1을 추가해준다.
                apartNum.append(1)
                res += 1
            else:
                apartNum.append(dfsRes)         # 단지 내의 아파트의 수를 리스트에 추가
                res += 1                        # 단지 수 추가

print(res)
apartNum.sort()
for ans in apartNum:
    print(ans)