BAEKJOON/알고리즘

[BOJ] 1012번 : 유기농 배추

말하는 알감자 2024. 1. 3. 17:00




📌 풀이

문제 자체는 어렵지 않았지만, 좌표를 행렬에 대입해서 생각할 때 오류를 조금 범했다.

가로의 길이가 M이고 세로의 길이가 N인 직사각형의 경우 좌표가 (x,y)라면, 행렬의 경우 matrix[y][x]와 같다.

좌표를 행렬에 대입해서 생각하면, x좌표는 열, y좌표는 행이 되는 것이다.

그래서 아래 그림처럼 N행 M열인 행렬 (가로 M 세로 N인 행렬)을 transpose 시켜서, M행 N열인 행렬로 바꿔서 풀었다.

이렇게 행렬을 바꿔놓으면 별 문제 없이 코드가 작동하는 것을 알 수 있다.

🔑 python 코드

# 유기농 배추
import sys
from collections import deque
input = sys.stdin.readline
T = int(input())

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    graph[x][y] = 0 # 탐색한 부분 재탐색 안하려고

    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(nx < 0 or ny <0 or nx >= M or ny >= N):
                continue

            if(graph[nx][ny] == 1):
                queue.append((nx, ny))
                graph[nx][ny] = 0 # 탐색한 부분 재탐색 안하려고



for _ in range(T):
    M, N, K = map(int, input().split())
    graph = [[0 for _ in range(N)] for _ in range(M)]
    cnt = 0
    for _ in range(K):
        x, y = map(int, input().split())
        graph[x][y] = 1

    for i in range(M):
        for j in range(N):
            if(graph[i][j] == 1):
                cnt += 1
                bfs(i, j)
    print(cnt)

게시글이 싹 날라가서 다시 다 적었다 눈물이 난다.

'BAEKJOON > 알고리즘' 카테고리의 다른 글

[BOJ] 1974번 : Z  (0) 2024.01.28
[BOJ] 16953번 : A -> B  (1) 2024.01.22
[BOJ] 2667번 : 단지 번호 붙이기  (1) 2024.01.02
[BOJ] 11725번 : 트리의 부모 찾기  (1) 2024.01.01
[BOJ] 1717번 : 집합의 표현  (1) 2023.12.30