1012번: 유기농 배추

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

 

문제는 저번에 푼 것과 다를 게 없는데 자꾸 원하지 않는 답이 나와서 왜 그런지 분석하느라 오래걸렸다.

MAP 정보를 전부 입력한 후 graph 생성을 했어야 했는데 for문에서 돌면서 MAP 정보를 입력하면서 graph 생성을 해서

올바른 graph가 생성되지 않았었다.. 이 문제를 해결하는 데에 2시간이나 걸렸다...

 

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

import sys
from collections import defaultdict, deque

T = int(input())
dx = [0, 0, -1, 1] # 상 하 좌 우
dy = [-1, 1, 0, 0] # 상 하 좌 우

def BFS(start, graph, num, visited) :
    visited[start[0]][start[1]] = 1
    q = deque([start])
    while q :
        u = q.popleft()
        visited[u[0]][u[1]] = 1
        for e in graph[u] :
            if visited[e[0]][e[1]] == 0 :
                visited[e[0]][e[1]] = 1
                q.append(e)
    return num + 1

for t in range(T) :
    M, N, K = map(int, sys.stdin.readline().split())
    MAP = [[0 for _ in range(M+2)] for _ in range(N+2)]
    graph = defaultdict(list)
    num = 0
    for k in range(K) :
        m, n = map(int, sys.stdin.readline().split())
        MAP[n+1][m+1] = 1
    # graph 설정
    for n in range(N) :
        for m in range(M) :
            if MAP[n+1][m+1] == 1 :
                graph[(n+1, m+1)].append((n+1, m+1))
                for idx in range(4) :
                    new_n = n + 1 + dy[idx]
                    new_m = m + 1 + dx[idx]
                    if MAP[new_n][new_m] == 1 :
                        graph[(n+1, m+1)].append((new_n, new_m))
    
    # BFS
    visited = [[0 for _ in range(M+2)] for _ in range(N+2)]
    for key in graph :
        if visited[key[0]][key[1]] == 0 :
            num = BFS(key, graph, num, visited)

    print(num)

 

상하좌우에 연결된 노드가 있는지 확인할 때 index error가 생기는 것을 방지하기 위해 현재 위치가 가생이에 있는지 확인하는 if문을 없애보았다.

N, M 행렬이 아닌 N+2, M+2 사이즈의 행렬을 생성하여 더미 가생이를 주었다!