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

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

2667번: 단지번호붙이기

---

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

 

해설

연달아 DFS 문제만 계속 나오고 있다. 해당 문제는 이전에 대부분 경험했던 유형이라 특별하게 어려운 부분이 없었다.

1. 방문하여 집이 있는 곳은 방문표시하기

2. 1번을 기준으로 상하좌우에 집이 있나 확인하기

3. 집이 있다면, 해당 집으로 방문하면서 단지수 1 증가시키기

4. 1~3 과정을 반복하여 최종 단지수 반환

5. 전체 지도에 1~4 과정을 반복하여 영역 분리하기

 

코드

import sys
sys.setrecursionlimit(100000)

N = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(N)]

d = [(0,1), (0,-1), (1,0), (-1,0)]
def dfs(x, y, cnt):
    graph[y][x] = 0
    for dx, dy in d:
        X, Y = x + dx, y + dy
        if (0 <= X < N) and (0 <= Y < N) and graph[Y][X]:
            cnt = dfs(X, Y, cnt+1)
    return cnt
          
cnt = []

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

cnt.sort()
print(len(cnt))
for i in range(len(cnt)):
    print(cnt[i])

 

풀이

import sys
sys.setrecursionlimit(100000)

N = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(N)]

1. 입력을 받는 부분이다.

집의 유무를 1, 0으로 입력받는다.

이 때 값을 정수형으로 분리하여 리스트에 저장하기 위해 map 메서드도 함께 사용해준다.

[python] 파이썬 숫자 각 자리수 분리

 

d = [(0,1), (0,-1), (1,0), (-1,0)]
def dfs(x, y, cnt):
    graph[y][x] = 0
    for dx, dy in d:
        X, Y = x + dx, y + dy
        if (0 <= X < N) and (0 <= Y < N) and graph[Y][X]:
            cnt = dfs(X, Y, cnt+1)
    return cnt

2. 방문했을 경우 0으로 표시해준다.

상하좌우를 돌면서 연결되어 있는 집으로 이동하고, 단지수를 1 증가시켜 재귀호출해주며,

그 값을 저장하여 반환하도록 하여 재귀호출하여도 그 값이 유지되도록 한다.

 

cnt = []

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

cnt.sort()
print(len(cnt))
for i in range(len(cnt)):
    print(cnt[i])

3. 지도를 돌면서 집이 있을 경우 dfs를 호출하여 반환된 단지 수를 리스트에 저장한다.

오름차순으로 정렬하여 문제 조건에 맞게 출력해준다.

 

피드백

문제를 풀다가 어려우면 다른 블로그들을 찾아보는데, 대부분 설명은 간략하고 코드만 작성되어 있는 경우가 많았다.

쉬운거면 상관 없는데, 이런 어려운건 어떻게 푼건지 코드를 해석해보는게 초보인 나에게는 불친절하게 느껴졌다.

그런데, 계속 반복되는 유형의 문제를 풀다보니 나도 점점 설명이 짧아질 수 밖에 없는 것 같다.

그들도 처음엔 길었겠지 ㅠㅠ

 

몰랐었는데, 계속 내 코드가 조회되길래 찾아보니까 파이썬 실행시간 1등이었다 ㄷㄷ 왜지?