백준 1926: 그림

아이디어

그래프 탐색

인접한 모든 부분들을 탐색하는 문제이므로 BFS 또는 DFS.

BFS, DFS 모두 다음과 같은 과정

• 시작노드 방문 체크, 시작노드 큐 또는 스택에 삽입
• 이후 큐 또는 스택이 빌때까지 while문 반복
• (1) 가공: 노드를 꺼내서 현재 노드로 정의하고 결과에 저장
• (2) 체크 및 삽입: 현재 노드의 이웃을 for 루프로 탐색하고, 체크 되지 않은 이웃 체크 후 삽입

노드와 이웃의 표현

이 문제에서 노드는 1, 2, 3 처럼 숫자 하나로 표현되지 않음.

대신 행, 열 좌표로 표현.

current_node 대신 current_row, current_col

start_node 대신 start_row, start_col

이웃이란, 현재 노드에서 상하좌우 1칸을 움직여 도달할 수 있으며 값이 1인 것.

neighbor_row, neighbor_col = current_row, current_col + 1칸

if 2차원 리스트[행][열] == 1.

행, 열의 범위: 0 ≤ 행, 열 < n, m

시작점 하나마다 그림 개수 + 1, 최대 크기 업데이트

2중 for 루프로 모든 시작점에 대해 bfs, 그림 크기를 결과로 얻고, 0 보다 크면 개수 + 1

업데이트: 최대 크기 = max(최대 크기, 현재 크기)

코드 구현

입력

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
space = [list(map(int, input().split())) for _ in range(n)]

BFS 구현

from collections import deque

neighbors = [[], [2, 3, 4], [1, 5], [1], [1], [2]]
visited = [False] * 6

start_node = 1
result = []

# Start: Check & Insert
visited[start_node] = True 
queue = deque([start_node])

while queue: # Until queue is empty (All reachable nodes are visited)
    
    # Process
    current_node = queue.popleft()
    result.append(current_node)

    # Neighbor: Check & Insert
    for neighbor in neighbors[current_node]:
        if not visited[neighbor]:
            visited[neighbor] = True
            queue.append(neighbor)

print(result)

문제에 맞게 개조

주의점: 방문 여부 체크 전 범위 체크해야 됨 (인덱스 에러 방지). 노드 값이 1인지도 체크 필요.

visited = [[False] * m for _ in range(n)]
delta_row = [1, -1, 0, 0]
delta_col = [0, 0, 1, -1]

start_row, start_col = 0, 0
size = 0

# Start: Check & Insert
visited[start_row][start_col] = True 
queue = deque([(start_row, start_col)])

while queue: # Until queue is empty (All reachable nodes are visited)
    
    # Process
    current_row, current_col = queue.popleft()
    size += 1

    # Neighbor: Check & Insert
    for i in range(4):
        neighbor_row = current_row + delta_row[i]
        neighbor_col = current_col + delta_col[i]
        if 0 <= neighbor_row < n and 0 <= neighbor_col < m and space[neighbor_row][neighbor_col] == 1:
            if not visited[neighbor_row][neighbor_col]:
                visited[neighbor_row][neighbor_col] = True
                queue.append((neighbor_row, neighbor_col))

print(size)

반복 사용을 위해 모듈화

주의점: 시작을 deque([(start_row, start_col)])으로 고정할 것이 아니라 먼저 노드 값이 1인지 확인하고 큐에 추가하는 방식

def find_size(start_row, start_col):
    
    # Initialize 
    visited = [[False] * m for _ in range(n)]
    size = 0
    queue = deque()

    # Start: Check & Insert
    if space[start_row][start_col] == 1: # Proper start
        visited[start_row][start_col] = True
        queue.append((start_row, start_col))

    while queue: # Until queue is empty (All reachable nodes are visited)
        
        # Process
        current_row, current_col = queue.popleft()
        size += 1

        # Neighbor: Check & Insert
        delta_row = [1, -1, 0, 0]
        delta_col = [0, 0, 1, -1]
        for i in range(4):
            neighbor_row = current_row + delta_row[i]
            neighbor_col = current_col + delta_col[i]
            if 0 <= neighbor_row < n and 0 <= neighbor_col < m and space[neighbor_row][neighbor_col] == 1:
                if not visited[neighbor_row][neighbor_col]:
                    visited[neighbor_row][neighbor_col] = True
                    queue.append((neighbor_row, neighbor_col))
    return size

for i in range(n):
    for j in range(m):
        print(find_size(i, j), end=' ')

문제에 맞게 결과 출력

count = 0
max_size = 0
for i in range(n):
    for j in range(m):
        size = find_size(i, j)
        if size > 0: 
            count += 1
            max_size = max(max_size, find_size(i, j))

print(count)
print(max_size)

! 문제점: max_size는 출력이 잘 되는데, 그림 개수 count가 맞지 않음.

→ visited가 함수 내부에서 계속 초기화되어 이미 세었던 그림도 시작 노드가 1이기만 하면 중복으로 센다.

→ visited를 함수 외부에서 초기화, 탐색 전 방문 여부 체크

count = 0
max_size = 0
for i in range(n):
    for j in range(m):
        if visited[i][j] == False:
            size = find_size(i, j)
            max_size = max(max_size, size)
            if size > 0: count += 1

print(count)
print(max_size)