2 분 소요

[Silver I] 단지번호붙이기 - 2667

문제 링크

성능 요약

메모리: 34096 KB, 시간: 60 ms

분류

너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 4월 15일 14:23:35

문제 설명

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

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

풀이

이제는 익숙할 만도 한 그래프문제이다. 너비우선탐색을 이용했다.

 N = int(input())
 Map = [[]for _ in range(N)]
 d = [(-1,0), (1,0), (0,-1), (0,1)]

 for i in range(N):
    temp = list(input().rstrip())
    for j in temp:
        Map[i].append(int(j))

지도의 크기와 지도의 내용을 입력받는다. 그리고 탐색할 방향도 리스트로 초기화해준다. 반복문을 이용해서 한줄씩 temp에 입력을 받고 문자들을 정수로 변환해준 다음에 Map에 저장하는 방식으로 작성했다.


 def BFS(a,b):
    q = deque([(a,b)])
    cnt = 0
    while q:
        x, y = q.popleft()

        for dx, dy in d:
            nx, ny = x+dx, y+dy

            if 0<=nx<N and 0<=ny<N:
                if Map[nx][ny]:
                    q.append((nx,ny))
                    cnt += 1
                Map[nx][ny] = 0
    if not cnt: return 1
    else: return cnt

BFS함수이다. 행과 열 인덱스 a,b를 인자로 받고 탐색 지점으로 설정한다. 그리고 이동위치가 1인 곳으로 상하좌우 1칸씩 이동하며 인접한 집을 모두 탐색한다. 인접한 집을 찾을 때마다 cnt의 증가연산으로 개수를 세준다. 탐색이 끝난 후에는 0으로 저장함으로써 다음 탐색에 중복되지 않도록 한다.

모든 탐색을 마친 후에는 해당 단지안의 집 개수를 출력하는데, 집이 1곳인 단지의 경우에는 주변에 집이 없으므로, cnt변수가 0이 되버린다. 따라서 집이 1인 경우는 1을 리턴해주고 1이 아닌 경우는 계산한 cnt값을 리턴해준다.


 res = []
 for i in range(N):
    for j in range(N):
        if Map[i][j]:
            res.append(BFS(i,j))
            
 res = sorted(res)
 L = len(res)

 print(L)
 for k in range(L):
    print(res[k])

마지막으로 이중반복문을 통해 집이 있는 곳에서부터 BFS함수를 실행하고 리턴값을 res에 추가한다. 출력조건이 오름차 순이므로 res를 정렬해준 후 단지의 개수와 각 단지마다 집의 개수를 출력해준다.

전체 코드

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
Map = [[]for _ in range(N)]
d = [(-1,0), (1,0), (0,-1), (0,1)]

for i in range(N):
    temp = list(input().rstrip())
    for j in temp:
        Map[i].append(int(j))

def BFS(a,b):
    q = deque([(a,b)])
    cnt = 0
    while q:
        x, y = q.popleft()

        for dx, dy in d:
            nx, ny = x+dx, y+dy

            if 0<=nx<N and 0<=ny<N:
                if Map[nx][ny]:
                    q.append((nx,ny))
                    cnt += 1
                Map[nx][ny] = 0
    if not cnt: return 1
    else: return cnt

res = []
for i in range(N):
    for j in range(N):
        if Map[i][j]:
            res.append(BFS(i,j))
            
res = sorted(res)
L = len(res)

print(L)
for k in range(L):
    print(res[k])

댓글남기기

참고