[BOJ/Python] 1012 : 유기농 배추

👉 문제 링크

🤔 x,y를 뒤집어서 넣어야 하는 이유

좌표에서는 x좌표를 왼쪽에서 오른쪽으로, y좌표를 아래에서 위로 넣어주고,
배열에서는 x좌표를 위에서 아래로, y좌표를 왼쪽에서 오른쪽으로 넣어준다.

뒤집어서 안넣어줘서 시간이 꽤나 걸렸다. 혹시 나처럼 삽질하는 사람이 있을까 첨부!

👉 전체 코드

BFS

import sys
input = sys.stdin.readline
from collections import deque

t = int(input())

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

# bfs
def bfs(x,y):
    que = deque()
    que.append((x,y))

    while que:
        x,y = que.popleft()

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

            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 1:
                que.append((nx,ny))
                graph[nx][ny] = 0

#입력
for _ in range(t):
    m,n,k = map(int, input().split())
    graph = [[0]*m for _ in range(n)]
    cnt = 0

    for _ in range(k):
        x,y = map(int, input().split())
        graph[y][x] = 1
    
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                bfs(i,j)
                cnt += 1
    
    print(cnt)

DFS

문제를 읽자마자 bfs로 풀어야지 하고 풀었지만, dfs로도 가능하다.
풀어보고 잊지말고 첨부해라 거북아