백준 - [Silver 1] 2667번 단지번호붙이기

문제링크: https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

dfs/bfs 기본문제를 풀어서 가장 유명한 문제인 단지 번호 붙이기 문제를 풀었습니다.

 

---

문제 설명

- 맵의 길이(N)이 주어짐 N * N

- 1은 집이 있는 곳으로 단지를 구분해주어 개수를 오름차순으로 출력해주는 문제

단지 구분 예시

---

풀이 방법

DFS / BFS 기본 문제

- 저는 queue를 사용하여 bfs로 풀이하였습니다.

- 상하좌우 4가지 방향을 방문 하며 순회하면 된다.

- visited로 방문체크를 굳이 하지 않고 직접 MAP에 0으로 바꾸어 주어도 되는데 습관이라 그냥 놔뒀다.

from sys import stdin
from collections import deque
# stdin = open("input.txt", "r")

# 방향: ^ > v <
direction = ((0, 1), (1, 0), (0, -1), (-1, 0)) 

def bfs(x, y):

    queue = deque()
    queue.append((x, y))
    visited[x][y] = True

    count = 1

    while queue:

        x, y = queue.popleft()
    
        # 4가지 방향 전부 탐색
        for d in direction:
            move_x = x + d[0]
            move_y = y + d[1]
            # 맵에 있고 방문되지 않고 집이면
            if 0 <= move_x < N and 0 <= move_y < N and \
                not visited[move_x][move_y] and MAP[move_x][move_y] == 1:
                queue.append((move_x, move_y))
                # 방문 체크하고 큐에 추가
                visited[move_x][move_y] = True
                count += 1

    return count

# N: 지도의 크기
N = int(stdin.readline())
# 2차원 배열로 입력받기
MAP = [list(map(int, stdin.readline().strip())) for _ in range(N)]
# 방문 체크 배열
visited = [[False] * N for _ in range(N)]

apart = []
for i in range(N):
    for j in range(N):
        if MAP[i][j] == 1 and not visited[i][j]:
            apart.append(bfs(i, j))

# 오름차순 정렬
apart.sort()
# 아파트 개수 출력
print(len(apart))
for a in apart:
    print(a)

 

코드: https://github.com/smothly/Algorithm_Solving/blob/master/boj-2667.py