📌 풀이
문제 자체는 어렵지 않았지만, 좌표를 행렬에 대입해서 생각할 때 오류를 조금 범했다.
가로의 길이가 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 |