[백준] 단지번호 붙이기

최동혁·2022년 12월 6일

백준

목록 보기

34/68

단지번호붙이기

solved_ac[Class3][단지번호붙이기](https://www.acmicpc.net/problem/2667)

문제

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

입력

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

출력

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

예제 입력 1

예제 출력 1

문제 해석

붙어 있는 모든 노드의 수를 세는 문제이다. DFS와 BFS 둘다 이용해서 풀어도 되지만 나는 BFS로 풀었다. [백준]1260번: DFS와 BFS에서 설명을 했고, [백준]2606번: 바이러스에서 DFS와 BFS의 차이점과 어떤 문제 유형에서 어떤 알고리즘을 써야하는지에 대해서 기술해놨으니 찾아보도록 하자.

풀이

지도 리스트를 graph에 저장해준다.
함수(bfs) 선언
- 상, 하, 좌, 우를 탐색할 것이기 때문에 dx 배열과 dy 배열 선언
- 시작 좌표값은 이미 아파트가 있기 때문에 queue에 집어넣어주고 이 아파트 단지의 아파트 수를 세기 위한 res_cnt 변수를 1 올려준다.
- 그리고 해당 좌표의 값을 2로 바꾸어준다.
- 왜냐면 한 단지를 탐색하고 다른 단지를 찾을 때 값이 1인 것을 찾아서 집어넣어줄 것이기 때문에 방문을 했다는 근거로 1이 아닌 값으로 바꾸어 주는것이다.
- queue가 빌 때까지 루프
  - 큐에 들어와 있는 좌표를 뺀다.
  - 상, 하, 좌, 우 를 위한 4번 루프
    - nx, ny를 업데이트 해주면서 해당 graph[nx][ny]가 1인지 체크한다.
    - 만약 1이면?
      - queue에 해당 좌표를 넣어준다.
      - 방문을 했기 때문에 graph[nx][ny] 값을 2로 바꾸어준다.
      - 아파트 수를 세기 위한 res_cnt 변수를 1 올려준다.
N x N 루프를 돈다.
- 만약 graph[i][j] 값이 1이라면?
  - 해당 아파트는 아직 숫자를 세지 않았기 때문에 bfs()함수를 호출한다.
  - bfs 함수를 한번 호출하면 한 단지의 아파트 수를 세서 res 배열에 넣어주게 된다.
res 배열을 오름차순으로 정렬을 해준다.
res 배열의 길이가 아파트 단지 수이기 때문에 출력
정렬한 숫자들을 출력.

시간 초과 코드

import sys
from collections import deque

N = int(sys.stdin.readline())

graph = []

for i in range(N):
    graph.append(list(map(int, sys.stdin.readline().rstrip())))

queue = deque()
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
queue.append([0,0])
res_cnt = 0
tot_cnt = 0
brk = False
res = []

if graph[0][0] == 1:
    res_cnt += 1

while True:
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx >= 0 and nx < N and ny >= 0 and ny < N:
                if graph[ny][nx] == 1:
                    queue.append([nx, ny])
                    graph[ny][nx] = 2
                    res_cnt += 1
    res.append(res_cnt)
    res_cnt = 0
    tot_cnt += 1
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 1:
                queue.append([j, i])
                brk = True
                break
        if brk == True:
            brk = False
            break
        if i == N - 1:
            brk = True
    
    if brk == True:
        print(tot_cnt)
        break
                
res.sort(reverse = False)

for i in res:
    print(i)

정답 코드

import sys
from collections import deque

N = int(sys.stdin.readline())

graph = []

for i in range(N):
    graph.append(list(map(int, sys.stdin.readline().rstrip())))

res = []

def bfs(graph, x, y, res):
    queue = deque()
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    
    queue.append([x, y])
    res_cnt = 1
    graph[x][y] = 2
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx >= 0 and nx < N and ny >= 0 and ny < N:
                if graph[nx][ny] == 1:
                    queue.append([nx, ny])
                    graph[nx][ny] = 2
                    res_cnt += 1
    res.append(res_cnt)
    
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            bfs(graph, i, j, res)
res.sort()
print(len(res))
for i in res:
    print(i)