백준 1012번 유기농 배추 파이썬

리뷰

BFS를 사용하여 풀었다, x, y축 잡는게 아직까진 헷갈리는 것 같다.

 

문제 풀이

1. 테스트 케이스의 수와 방향을 나타낼 리스트를 초기화 해준다.
2. m * n크기의 2차원 배열을 0으로 초기화 하고, 방문을 나타낼 배열도 동일한 크기, False로 초기화 해준다.
3. 이후 배추의 위치를 받아와 해당 위치를 2차원 배열에 1로 최신화 해준다.
4. 이후 배열 전체를 돌며 bfs를 실행해준다.

 

참고 사항

x와 관련된 행은 n이고 y와 관련된 행은 m이다.

 

 

정답 코드

from collections import deque

t = int(input())
dist = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for _ in range(t):
    m, n, k = map(int, input().split())
    lst = [[0] * m for _ in range(n)]
    v = [[False] * m for _ in range(n)]
    for _ in range(k):
        x, y = map(int, input().split())
        lst[y][x] = 1
    ans = 0


    def bfs(index):
        q = deque([index])
        v[index[0]][index[1]] = True
        while q:
            x, y = q.popleft()
            for dx, dy in dist:
                nx = x + dx
                ny = y + dy
                if 0 <= nx < n and 0 <= ny < m and not v[nx][ny] and lst[nx][ny]:
                    v[nx][ny] = True
                    q.append((nx, ny))


    for i in range(n):
        for j in range(m):
            if not v[i][j] and lst[i][j] == 1:
                bfs((i, j))
                ans += 1
    print(ans)