BOJ1012 유기농 배추

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

1012번: 유기농 배추

 

난이도: 실버2

소요시간: 45분

아래는 나의 코드이다. nq 변수에 값을 잘못 저장하여 에러잡느라 시간을 예상치 못하게 많이 잡아 먹었다...

import sys
from collections import deque
T = int(sys.stdin.readline())
move=[[1,0],[-1,0],[0,1],[0,-1]]

def BFS(start):
    que= deque([start])
    if visited[start[0]][start[1]] == True:
        return 0;

    if myMap[start[0]][start[1]] == 0:
        visited[start[0]][start[1]] = True
        return 0;

    while que:
        q=que.popleft()

        if visited[q[0]][q[1]] == True:
            continue
        visited[q[0]][q[1]] = True
        for m in move:
            nq=[q[0]+m[0],q[1]+m[1]]
            if nq[0] >= M or nq[1] >= N or nq[0] < 0 or nq[1] < 0:
                continue
            if myMap[nq[0]][nq[1]] == 1:
                que.append(nq)
    return 1;


for _ in range(T):
    M,N,K = map(int,sys.stdin.readline().split())
    myMap=[[0 for _ in range(N)]for _ in range(M)]
    visited=[[False for _ in range(N)]for _ in range(M)]
    for i in range(K):
        temp=list(map(int,sys.stdin.readline().split()))
        myMap[temp[0]][temp[1]] = 1
    result=0
    for i in range(M):
        for j in range(N):
            result+=BFS([i,j])

    print(result)

위의 코드는 map을 전체 순환하면서 0이면 바로 넘어가고 1이라면 그자리에서 탐색을 시작하는 구조이다. 하지만 이걸 조금 더 좋게 수정하면 0이여도 bfs탐색을 시작하여 전부 방문처리하면 되겠다.... 라고 생각했는데 다시 생각해보니. 결국 같은 시간복잡도인 것같다.