[파이썬] 백준 1012 : 유기농 배추

[파이썬] 백준 1012 : 유기농 배추

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

1012번: 유기농 배추

실버 2

그래프 이론, DFS, BFS

---

런타임 에러가 발생할 수 있으므로 

sys.setrecursionlimit(10 ** 6)

와 같은 값을 넣어주는 것이 좋다.

 

DFS의 방법을 활용해서 구하는 문제로, dfs기능을 하는 함수 내에서 좌표를 이동하는 방법을 고안해야 한다.

 

코드

import sys; input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def dfs(x,y):
    dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if nx >= N or nx < 0 or ny >= M or ny < 0 or visited[nx][ny]:
            continue
        if field[nx][ny] != 0:
            visited[nx][ny] = 1
            dfs(nx, ny)

T = int(input())
for _ in range(T):
    M, N, K = map(int,input().split())
    field = [[0] * M for _ in range(N)]
    visited = [[0] * M for _ in range(N)]
    ans = 0
    for _ in range(K):
        a, b = map(int,input().split())
        field[b][a] = 1
    for i in range(N):
        for j in range(M):
            if field[i][j] and not visited[i][j]:
                visited[i][j] = 1
                ans += 1
                dfs(i,j)
    print(ans)

 

def dfs(x,y):
    dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if nx >= N or nx < 0 or ny >= M or ny < 0 or visited[nx][ny]:
            continue
        if field[nx][ny] != 0:
            visited[nx][ny] = 1
            dfs(nx, ny)

 

좌표 값을 한 칸씩 이동하며 설정한 그래프 범위를 벗어나거나 이미 방문한 좌표의 경우를 건너뛰도록 한다.

만약 이동한 좌표에 배추가 존재하고 방문되지 않았다면 방문처리를 하고 dfs를 재귀로 다시 돌린다.

 

T = int(input())
for _ in range(T):
    M, N, K = map(int,input().split())
    field = [[0] * M for _ in range(N)]
    visited = [[0] * M for _ in range(N)]
    ans = 0
    for _ in range(K):
        a, b = map(int,input().split())
        field[b][a] = 1

 

field는 입력한 범위내의 좌표 값들을 2차원 배열로 그려낸다.

visited는 같은 범위의 좌표값에 대한 방문 처리를 담당하는 변수가 된다.

ans는 지렁이의 개수를 카운트 한다.

a, b를 입력받았을 때 field[b][a] = 1을 하는 이유는 다음과 같다.

0,0	1,0
0,1	1,1

컴퓨터 상에서의 좌표의 구현은 위와 같을 것이다.

이차원 배열로 1,0의 위치에 접근한다고 가정하면 가로는 0번째 칸, 세로는 1번째 칸에 있는 위치와 동일하다.

따라서 field[a][b]가 아니라 field[b][a]가 되는 것이다.

 

입력받은 값은 반드시 지렁이가 위치하게 되므로 해당 위치의 값을 1로 설정한다.

 

for i in range(N):
        for j in range(M):
            if field[i][j] and not visited[i][j]:
                visited[i][j] = 1
                ans += 1
                dfs(i,j)
    print(ans)

 

이차원 배열을 순회하면서 해당 위치에 배추가 존재하면서 방문처리가 되지 않은 좌표를 찾아냈다면, 그 위치를 방문처리하면서 지렁이가 한 마리 있음을 나타낸다. 또한 dfs함수를 실행하여 그 위치를 기점으로 해서 좌표 값을 하나씩 바꿔가며 배추가 있는지 없는지를 확인하게 될 것이다.

dfs가 한번 실행되면 지렁이가 1마리가 필요하므로 ans += 1을 해주고, 0인 부분을 찾았다면 dfs가 종료될 것이다.

다시 배추가 있는 미방문 좌표를 찾아냈다면 지렁이를 한 마리 더 추가시키고 0인 부분을 찾을 때까지 dfs 함수가 계속해서 실행될 것이다.

 

 

 

visited함수를 따로 사용하지 않는 방식의 풀이는 다음과 같다.

import sys; input = sys.stdin.readline
sys.setrecursionlimit(10**6)
def dfs(x, y):
    if x < 0 or x >= M or y < 0 or y >= N:
        return
    if graph[x][y] == 0:
        return
    graph[x][y] = 0
    
    dfs(x+1, y)
    dfs(x, y+1)
    dfs(x-1, y)
    dfs(x, y-1)
    
T = int(input())
for _ in range(T):
    N, M, K = map(int, input().split())
    graph = [[0]*N for _ in range(M)]
    result = 0
    for _ in range(K):
        x, y = map(int, input().split())
        graph[y][x] = 1
    
    for x in range(M):
        for y in range(N):
            if graph[x][y] == 1:
                dfs(x, y)
                result += 1
    print(result)

 

좌표가 범위를 벗어나거나 0인 경우는 건너뛰면서 dfs가 진행된다. 이때, 방문처리는 해당 좌표의 graph값을 0으로 설정하는 방법으로 한다.