[Python] BOJ 1926 : 그림

요구사항, 설계

• 2차원 배열의 최대 크기가 2500이다. 시간 메모리 걱정 없다.
• 5분 생각하고 안 떠올라서 답지 봤다.

구현

from collections import deque

# 가로 세로 크기
n, m = map(int, input().split())

# 도화지
canvas = [list(map(int, input().split())) for _ in range(n)]

# 방문 여부
visited = [[False] * m for _ in range(n)]

# 그림의 개수
num_of_pictures = 0

# 가장 넓은 그림
max_size = 0

def bfs(x, y):
    queue = deque([(x, y)])
    visited[x][y] = True

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    size = 1 # 현재 도화지의 크기

    while queue:
        cx, cy = queue.popleft()
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 <= nx <n and 0 <= ny < m and not visited[nx][ny] and canvas[nx][ny] == 1:
                visited[nx][ny] = True
                queue.append((nx, ny))
                size += 1
    return size

for i in range(n):
    for j in range(m):
        if canvas[i][j] == 1 and not visited[i][j]:
            num_of_pictures += 1
            max_size = max(max_size, bfs(i, j))

print(num_of_pictures)
print(max_size)

• 답지 보니깐 하나씩 기억나서 익숙해 지려고 안보고 3번 정도 작성했다. 
• 좀 헷갈렸 던 건 dx,dy 상하좌우 확인하는 부분과 왜 visited를 두 번 처리해야되나 생각했다.
• 상하 좌우 코드

# 현재 위치
x, y = 2, 2

# 상하좌우 이동을 위한 방향 벡터
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 상하좌우 이동
for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    print(f"이동 방향 {i+1}: ({nx}, {ny})")

• 그냥 뭐 찍어봤는 데 아 그렇게 찍히는 구나. 외워서 그냥 요정에 맡긴다 생각하자. 
• 상하 좌우 확인 하는 문제는 많기 때문에 딱 기본 틀만 외우고 나머지는 상황별로 살을 붙이면 좋을 듯하다. 
• 왜 visited 를 두 번 처리해야 되느냐?
• 2중 for문이 돌면서 canvas가 1 인지와 방문여부가 거짓일 때 
• bfs 함수로 들어간다.
• 이 때 들어가자마자 방문처리를 해줘야 들어간 좌표를 제외한 나머지의 상하 좌우를 확인할 수 있다.

앞으로 

앞으로 BFS 유형만 풀게 될 텐데 한 유형에 계속 익숙해질 때까지 더 풀어보자. 

고민이 되는 부분은 한 유형을 계속 알 때까지 파보는 것과 여러 유형을 한 개씩 풀어보는 게 도움이 될지.

음... 내 생각에는 한 유형씩 익숙해지고 대부분의 유형이 익숙해질 때 쯤 여러 유형을 한 개씩 풀어보는 게 나을 거 같다.