[DFS/BFS] 단지번호 붙이기 (BOJ 2667, 실버 1)

DFS / BFS의 정석 문제이다 😎

문제

https://www.acmicpc.net/problem/2667

• 지도 속 아파트 단지 모임의 개수와 각 모임 별 단지의 개수를 출력해라.
• 단, 단지의 개수는 오름차순으로 출력해라.

코드

정답 코드

from collections import deque
cnt = 0

def solution():
    global cnt
    answer = []
    N = int(input())

    graph = [list(map(int, input())) for _ in range(N)]
    visited = [[0]*N for _ in range(N)]

    for i in range(N):
        for j in range(N):
            if visited[i][j] == 0 and graph[i][j] == 1:
                dfs(i, j, graph, visited, N)
                answer.append(cnt)

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


def dfs(x, y, graph, visited, N):
    global cnt
    cnt = 0     # 한 영역 당 단지 개수

    queue = deque()
    queue.append((x, y))
    visited[x][y] = 1       # visited 1이면 다시 방문하지 않음
    cnt += 1

    dx = [0, 0, -1, 1]      # 상하좌우
    dy = [-1, 1, 0, 0]

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
        
            if 0 <= nx < N and 0 <= ny < N:
                if visited[nx][ny] == 0 and graph[nx][ny] == 1:
                    queue.append((nx, ny))
                    visited[nx][ny] = 1
                    cnt += 1

solution()

기억할 점

• 계속해서 프로그래머스 환경에서 문제를 풀다가 오랜만에 백준 문제를 풀어보니 입출력 부분에서 조금 헤매게 되었다. 백준 방식의 입출력도 꾸준히 보면서 잊지 말아야 겠다!!

graph 입력 받기 초기 코드

    # 처음엔 아래처럼 코드를 작성해서
    # 그래프에 숫자가 int형이 아닌 str형으로 저장돼서 아예 0 또는 1로 인식이 안됨
    for i in range(N):
        s = input()
        s_list = []
        for j in range(N):
            s_list.append(s[j])
        graph.append(s_list)

• 추가로 문제 요건들을 꼼꼼히 읽지 않아 해당 부분들을 바로 잡는데 오래 걸렸다.
  ex) 단지 개수를 오름차순으로 출력하기 등
  실제 문제를 풀 때 문제를 더 꼼꼼히 읽으면서 조건들을 잘 체크해야 겠다.