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

문제

---

 

1012번: 유기농 배추

코드

---

My answer

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

t=int(input())
direct=[[-1,0],[1,0],[0,-1],[0,1]]

def dfs(idx1,idx2):
    visit[idx1][idx2]=1
    for i in direct:
        n_idx1=idx1+i[0]
        n_idx2=idx2+i[1]
        if(n_idx1>=0 and n_idx1<m and n_idx2>=0 and n_idx2<n):
            if(visit[n_idx1][n_idx2]==0 and graph[n_idx1][n_idx2]==1):
                dfs(n_idx1,n_idx2)
    #print("here", idx1,idx2)
    return 0

def bfs(idx1,idx2):
    Q=deque()
    Q.append((idx1,idx2))
    while Q:
        idx1, idx2 = Q.popleft()
        visit[idx1][idx2]=1
        for i in direct:
            n_idx1=idx1+i[0]
            n_idx2=idx2+i[1]
            if(n_idx1>=0 and n_idx1<m and n_idx2>=0 and n_idx2<n):
                if(visit[n_idx1][n_idx2]==0 and graph[n_idx1][n_idx2]==1):
                    Q.append([n_idx1,n_idx2])
                    visit[n_idx1][n_idx2] = 1
    return 0

for i in range(t):
    
    m,n,k=map(int,input().split())
    graph=[[0] * n for _ in range(m)]
    visit=[[0] * n for _ in range(m)]
    cnt=0
    
    for j in range(k):
        a,b=map(int,input().split())
        graph[a][b]=1  
          
    for j in range(m):
        for k in range(n):
            if(visit[j][k]==0 and graph[j][k]==1):
                #dfs(j,k)
                bfs(j,k)
                cnt+=1  
    print(cnt)

 

풀이

---

우선 나는 dfs로 풀었는데, 테스트케이스나 질문게시판의 반례가 전부 통과하고 잘 푼 것 같은데 recursion error가 떠서 알아보니 백준에서는 재귀함수의 최대호출을 1000으로 설정해놨다고 한다. 따라서 이 제한값을 변경하거나 다른 방법으로 문제를 풀어야한다. https://www.acmicpc.net/board/view/110963 나는 우선 제한을 m과n의최대값이 50*50이므로, 2501로 설정하여 성공했다. 우선 내 풀이를 먼저 설명하고 다른분들의 풀이와 다른 방법으로 또 풀어보도록 하겠다. 

내 풀이(dfs)

graph라는 빈 배열과 visit이라는 0이 들어가 있는 배열을 m*n의 크기로 생성해준다. 이후 입력받은 배추의 위치를 graph에 저장해준다. 다음으로 모든 밭의 위치를 돌면서 배추가 심어져있는데 아직 방문하지 않은 경우 dfs 함수를 실행하게 된다.

dfs함수를 실행하면 상하좌우를 확인해야하므로, 상하좌우로 움직였을 때의 좌표변화를 담아놓은 direct리스트를 토대로, 우선 이동하는 범위가 밭 바깥으로 넘어가는지를 확인하고 넘어가지 않는다면 방문여부와 배추가 심어져있는지 여부를 확인한다. 이렇게 확인하면서 방문처리를 해주고, 함수가 끝나면 cnt를 1올린다. 그럼 특정 시작에서 이어진 부분들을 전부 visit처리 하고 cnt가 1올라가는 것이다. 이런식으로 계속 진행하면 된다.( 주석의 print here을 해제하면 어떤 순서로 진행되는지 볼 수 있다)

내 풀이(bfs)

똑같이 그래프를 생성해주고, 그냥 전형적인 bfs로 돌려주면 된다. 단 계속해서 시간초과가 떴었는데 31번째에 있는 visit[n_idx1][n_idx2] = 1 이걸 뺴먹어서 그런 것 같다. 

 

+ 2차원 배열 만들 때 아래와 같이 만드는 것과 recursionerror 해결방법만 좀 참고하면 될 것 같다.

array=[[0] * n for _ in range(m)]