[Python] 백준 1012번 - 유기농 배추

문제 https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

확실히 여러 번 푸니까 이제는 문제 접근법이 비교적 쉽게 생각난다.

물론 실버인 것도 한 몫했겠지만... ㅋㅋㅋ

 

보통 m=row, n=col으로 하는데 여기서는 m=col, n=row여서 헷갈렸다.

그것때문에 배열 인덱스를 몇 번이나 바꿔서 재실행했는지 모르겠다. ㅠㅠ

 

그 부분 빼고는 무난한 문제였다고 생각한다.

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

def bfs(row, col):
    global worm
    q = deque()
    q.append((row, col))
    visited[row][col] = 1
    while q:
        row, col = q.popleft()
        if row == m-1 and col == n-1:
            break
        
        dydx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for dy, dx in dydx:
            new_y = dy + row
            new_x = dx + col
            if -1 < new_y < len(field) and -1 < new_x < len(field[0]):
                if field[new_y][new_x] == 1 and not visited[new_y][new_x]:
                    visited[new_y][new_x] = 1
                    q.append((new_y, new_x))

t = int(input())
for i in range(t):
    m, n, k = map(int, input().split())
    field = [[0 for j in range(m)] for i in range(n)]
    visited = [[0 for j in range(m)] for i in range(n)]
    ans = 0
    for j in range(k):
        x, y = map(int, input().split())
        field[y][x] = 1
    for i in range(n):
        for j in range(m):
            if field[i][j] == 1 and not visited[i][j]:
                bfs(i, j)
                ans += 1
    print(ans)

 

 

 

---

 

 

 

#220123

 

bfs 간만에 풀었더니 기억이 안 나서 좀 헤맸다.

그래도 어찌저찌 한 번에 성공

전에 풀었을 땐 행렬 때문에 고생 좀 했던 것 같은데 지금 보면 왜 그랬는지 모르겠다.

 

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

def bfs(x, y):
    visited[x][y] = 1
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft()
        if x == m-1 and y == n-1:
            break
        dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for dx, dy in dxdy:
            new_x = x + dx
            new_y = y + dy
            if -1 < new_x < len(matrix) and -1 < new_y < len(matrix[0]):
                if matrix[new_x][new_y] == 1 and not visited[new_x][new_y]:
                    visited[new_x][new_y] = 1
                    q.append((new_x, new_y))
                

t = int(input()) #테스트 케이스 개수
for _ in range(t):
    m, n, k = map(int, input().split()) #m: 가로, n: 세로, k: 배추 심어진 위치 개수
    visited = [[0 for _ in range(n)] for _ in range(m)]
    matrix = [[0 for _ in range(n)] for _ in range(m)]
    worm = 0
    for _ in range(k):
        x, y = map(int, input().split())
        matrix[x][y] = 1

    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 1 and not visited[i][j]:
                bfs(i, j)
                worm += 1

    print(worm)