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

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

DFS/BFS

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

---

풀이

처음 푼 풀이

import sys
input = sys.stdin.readline

# 그래프의 연결 요소의 개수를 출력하고
# 각 연결 요소에 속한 노드 개수를 오름차순 출력하면 됨.
# 입력은 총 단지수와, 단지내 집의 유무 오름차순

def dfs(x, y):
    count = 1
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= nx < n and 0 <= ny < n and matrix[nx][ny] == 1:
            matrix[nx][ny] += 1

            count += dfs(nx, ny)
            # 내가 count를 1로 정의해뒀잖아!
            # 그러니까 이 경우는 그냥 저걸 하는 행위 자체가 count를 1 더해서 반환받는 거랑 같은 거지.
    return count

n = int(input())
matrix = [list(map(int, input().rstrip())) for _ in range(n)]

# 2. 상하좌우 델타값 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
counts = []
for i in range(n):
    for j in range(n):
        if matrix[i][j] == 1:
            matrix[i][j] += 1
            counts.append(dfs(i, j))

print(len(counts))
print(*sorted(counts), sep = '\n')

# 풀이2) dfs를 좀 더 직관적으로 짜 보았음.
import sys
input = sys.stdin.readline

# 그래프의 연결 요소의 개수를 출력하고
# 각 연결 요소에 속한 노드 개수를 오름차순 출력하면 됨.
# 입력은 총 단지수와, 단지내 집의 유무 오름차순

def dfs(x, y):
    global count
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= nx < n and 0 <= ny < n and matrix[nx][ny] == 1:
            matrix[nx][ny] += 1
            count += 1
            dfs(nx, ny)


n = int(input())
matrix = [list(map(int, input().rstrip())) for _ in range(n)]

# 2. 상하좌우 델타값 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
counts = []
for i in range(n):
    for j in range(n):
        count = 1
        if matrix[i][j] == 1:
            matrix[i][j] += 1
            dfs(i, j)
            counts.append(count)

print(len(counts))
print(*sorted(counts), sep = '\n')

강사님 풀이 확인

import sys

input = sys.stdin.readline


def dfs(x, y):
    global house
    house += 1

    for k in range(4):
        nx, ny = x + dx[k], y + dy[k]

        if 0 <= nx < n and 0 <= ny < n and board[nx][ny] > 0:
            board[nx][ny] = 0
            dfs(nx, ny)


n = int(input())
board = [list(map(int, input().rstrip())) for _ in range(n)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
result = []

for i in range(n):
    for j in range(n):
        if board[i][j] > 0:
            house = 0
            board[i][j] = 0
            dfs(i, j)
            result.append(house)

print(len(result))
print(*sorted(result), sep="\n")

1. 집 개수 +1 하는 걸 dfs의 action 부분에서 바로 해버리면 초기값도 잡을 수 있었다. 굳이 방문x 인접 정점들로 이동 부분에서 action을 줄 필요는 없었음.
2. 내가 처음 한 것처럼 1 → 가능, 2 → 불가능 으로 나누기보단, 그냥 명확하게 1 → 가능, 0 → 불가능으로 나누는 게 더 나아보임.

---

250218 재풀이

import sys
input = sys.stdin.readline

n = int(input())
# n이 별로 안 큼 -> 그냥 n x n 반복문 돌리자.
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y):
    # 2. 재귀하며 현재 정점 action 실행
    global counts
    counts += 1
    # 3. 인접한 정점들에 대해,
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 4. 방문x 정점으로 이동하며 함수 호출
        if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 1:
            board[nx][ny] = 0
            dfs(nx, ny)

board = [list(map(int, list(input().rstrip()))) for _ in range(n)]
answer = []
for i in range(n):
    for j in range(n):
        if board[i][j] == 1:
            counts = 0
            # 1. 시작 정점 방문 처리
            board[i][j] = 0
            dfs(i, j)
            answer.append(counts)

print(len(answer))
print(*sorted(answer), sep = '\n')

bfs로도 풀이 가능