[Python] 백준 #1012 - 유기농 배추

문제

---

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

1012번: 유기농 배추

 

 

풀이

---

내 풀이 - DFS 사용

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

def dfs(x,y):
    visited[x][y] = True # 방문하였으니 True로 바꿔줌

    for i in range(4): # 상하좌우 방문 위해 4번 반복
        cx = x + dx[i] # 방문할 x좌표
        cy = y + dy[i] # 방문할 y좌표
        if 0<= cx < n and 0<= cy <m: # x좌표와 y좌표가 인덱스 범위 내에 있고
            if graph[cx][cy] == 1 and visited[cx][cy] == False: # 배추가 있고 지렁이가 방문하지 않았으면
                dfs(cx,cy) # 방문한 좌표의 상하좌우를 구해주기 위해 재귀
    
    

n = int(input())

for i in range(n):
    m,n,k = map(int,input().split())

    graph = [[0 for _ in range(m)] for _ in range(n)] # 배추가 심어진 땅
    visited = [[False for _ in range(m)] for _ in range(n)] # 지렁이 방문

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

    dx = [0,1,-1,0] # 상하좌우 x좌표
    dy = [1,0,0,-1] # 상하좌우 y좌표
    cnt=0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1 and visited[i][j] == False: # 배추가 심어져있고 지렁이가 방문하지 않았으면
                dfs(i,j) # 인접한 배추들을 다 구하기 위해 dfs 호출
                cnt+=1
    print(cnt)

 

지렁이가 방문할 수 있는 인접 배추를 dfs로 방문하여 구해주었다. 재귀깊이 때문에 런타임 에러 오류가 나서 setrecursionlimit를 10**6으로 설정해주었다.

 

먼저 주어진 크기만큼 이중리스트를 만들어주었다. graph가 배추가 심어진 땅이고 visited가 지렁이가 방문한 여부이다.

 

주어진 x,y값들로 배추의 위치를 1로 만들어주었다.

 

배추가 심어진 어떤 한 노드부터 시작하여 인접한 모든 노드를 구하기 위해서 dfs를 사용하였다. 이중 for문을 사용하여 배추가 심어져있고 아직 지렁이가 방문하지 않은 좌표를 구하여 dfs를 호출해준다.

 

dfs 함수 설명

방문한 좌표를 파라미터 x,y로 넘겨준다. x,y 위치는 방문하였으니 visited[x][y]를 True로 바꿔준다. 

상하좌우 방문을 하기 위하여 반복문을 4번 돌려주고 방문해야하는 위치를 cx,cy에 저장시켜준다. 

cx,cy가 인덱스 범위 내에 있는지 확인하고 범위 안이면 배추가 심어져있는지, 지렁이가 방문하지 않았는지를 체크한다.

만약 배추가 심어져있고 지렁이가 방문하지 않았다면 그 방문한 좌표의 인접한 배추를 구하기 위해 dfs를 호출한다.

 

 

dfs로 풀면 setrecursionlimit를 설정해주어야하기때문에 bfs로 푼 코드도 가져와봤다.

 

 

다른사람 풀이 - BFS 사용

from collections import deque
import sys
input = sys.stdin.readline

def bfs(x,y):
    queue = deque([[x,y]])
    graph[x][y] = 0

    while queue:
        a,b = queue[0][0], queue[0][1]
        queue.popleft()
        for i in range(4):
            cx = a + dx[i]
            cy = b + dy[i]
            if 0<=cx<n and 0<=cy<m and graph[cx][cy] == 1:
                graph[cx][cy] = 0
                queue.append([cx,cy])


n = int(input())
dx = [1,-1,0,0]
dy = [0,0,-1,1]
for i in range(n):
    m,n,k = map(int,input().split())
    graph = [[0]*m for _ in range(n)]
    cnt=0
    for j in range(k):
        x,y = map(int,input().split())
        graph[y][x] = 1
    
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                bfs(i,j)
                cnt+=1
    print(cnt)

 

방문하였으면 0으로 바꿔주는 식으로 푼 것이다.

 

 

출처 - https://pacific-ocean.tistory.com/270