[백준] 1012.유기농 배추

문제 바로가기

문제 풀이

bfs를 이용한 연결된 범위 탐색. 나는 visited와 graph를 따로 생각했는데 그냥 한 번에 생각해도되는 문제였다. bfs관련 문제들이 여전히 처음에 시작하는 것이 꺼려지지만 이전보다 많이 이해하고, 도전할 수 있어서 재미도 느끼고 있다.

정답 코드

"""
https://www.acmicpc.net/problem/1012
"""
from collections import deque

# idx에 따라 상하좌우
dx = [0,0,-1,1] 
dy = [1,-1,0,0]

N = int(input())

def bfs(graph, a, b):
    queue = deque()
    queue.append((a,b)) # 현재 위치
    graph[a][b] = 0 # graph에서 방문처리

    while queue:
        x, y = queue.popleft()
        for i in range(4): # 4방향 모두 탐색
            nx = x+dx[i]
            ny = y+dy[i]
            if nx < 0 or nx >=n or ny < 0 or ny >= m: # 범위 넘어서면 그냥 지나간다
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0 # 방문처리하고
                queue.append((nx, ny)) # 해당 위치 q에 append
    return

for i in range(N):
    cnt = 0
    n, m, k = map(int,input().split())
    graph = [[0]*m for _ in range(n)]

    for j in range(k):
        x, y = map(int, input().split())
        graph[x][y] = 1

    for a in range(n): # 1인 부분 만나면 연결된 부분 탐색(through bfs)
        for b in range(m):
            if graph[a][b] == 1:
                bfs(graph, a, b)
                cnt += 1
    print(cnt)

추가적인 개념 (optional)

import sys를 통해
input = sys.stdin.readline.strip()으로 실행했을 때 런타임에러가 발생했는데 그 이유가 무엇일까?
sys.stdin.readline은 python에서 input에서의 시간초과 문제 때문에 종종 사용했었다.
-> 아마원인은 strip()에서 있었을 것 같다. 가장 오른쪽의 공백(줄바꿈)만 삭제해주면 에러가 일어나지 않을 것 같다. (아님 여전히 발생함. 이유가 뭘까...)