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

- 문제 링크

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

- 풀이

그래프를 가로 x 세로 만큼 먼저 선언해놓고, K만큼 배추의 위치를 입력받을 때 graph 배열에 배추의 위치를 1로 표시한다.

그리고 배추가 있는 곳에서 bfs를 돌려주면 된다. 밑에 코드를 보면 알겠지만 배추의 위치를 입력받을 때 a, b 위치만 바꿔주는 것만 고려하면 특별히 예외처리 해줄만한 것도 없어서 푸는데 한.. 7분 걸렸던 것 같다. 

 

bfs를 한 번 실행할 때 마다 배추흰지렁이가 1마리씩 필요하다고 생각하면 편하다.

-  코드

import sys
from collections import deque
input = sys.stdin.readline
dx = [0,0,-1,1]
dy = [-1,1,0,0]

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = 1

    while queue:
        a, b = queue.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if graph[nx][ny] == 1 and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    queue.append((nx, ny))      


for _ in range(int(input())):
    M, N, K = map(int, input().split())
    graph = [[0] * M for _ in range(N)]
    visited = [[0] * M for _ in range(N)]
    for _ in range(K):
        a, b = map(int, input().split())
        graph[b][a] = 1
    cnt = 0
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1 and visited[i][j] == 0:
                bfs(i, j)
                cnt += 1
    print(cnt)

 

요즘 실버에서 골드 4까지의 문제를 랜덤으로 계속 반복해서 풀고 있다. 풀면서 느낀건 내가 재귀(백트래킹, dfs)에 많이 약하구나를 많이 느끼고 있다. 틈틈히 많이 공부해야겠다.. 해도해도 부족하지만 그래도 해야지 어쩌겠냐 !! 

아직 공부해야 될 것들 참 많지만 그래도 "꾸준히" 해나가야겠다 !!

 

리액트는 언제하지? ㅠㅠ