[Python] 백준 1012번 : 유기농 배추 (S2) - DFS&BFS단계별4

#문제

www.acmicpc.net/problem/1012

1012번: 유기농 배추

#풀이 & 학습한 내용

"땅의 모습이 아니라 배추의 위치가 주어지는 문제"입니다. 땅에서 배추의 위치를 2차원 리스트에 넣고, 이를 그래프로 생각하여 DFS를 수행해 문제를 해결하였습니다. 첫 번째 제출에서 런타임 에러(RecursionError)가 발생하여 재귀 깊이를 연장해주어 제출했지만, PyPy3에서 메모리 초과가 발생하여 Python3로 제출하니 통과되었습니다.

 

앞으로 파이썬의 재귀 깊이가 기본적으로 최대 1000으로 설정되어 있다는 점을 고려해야겠고, PyPy3에서 메모리 초과가 나올 때, Python3로도 제출해 봐야겠습니다.

cf) stackoverflow.com/questions/45117672/pypy-large-memory-usage-compared-to-cpython

PyPy large memory usage compared to CPython

#소스코드

import sys
sys.setrecursionlimit(10**9) #★재귀깊이 연장
 
dx=[0,0,1,-1]
dy=[1,-1,0,0] #상하좌우 방향 설정
 
#★ immutable object는 call by value이고 mutable object는 call by reference로
def dfs(i,j,area,visited):
  visited[i][j]=True #방문처리
  for k in range(4): #상하좌우 방향에 대해 for문
    x = i+dx[k]
    y = j+dy[k]
    if 0<=x<M and 0<=y<N and area[x][y]==1 and visited[x][y]==False:
      dfs(x,y,area,visited) #범위안에 있고, 배추있고, 방문 안했으면 재귀호출
 
 
T=int(input()) #테스트 케이스
for _ in range(T):
  worm = 0 #필요한 지렁이 수
  M,N,K = map(int,input().split())
 
  #배추 심어진 위치 저장하는 Adjacent Matrix
  area = [[0]*N for _ in range(M)]
 
  #Adjacent Matrix에서 방문여부 Check용
  visited = [[False]*N for _ in range(M)]
 
  #input으로 주어지는 배추 위치 저장
  for _ in range(K):
    i,j = map(int,input().split())
    area[i][j]=1
  
  for i in range(M):
    for j in range(N):
      if area[i][j]==1 and visited[i][j]==False:
        worm+=1
        dfs(i,j,area,visited) #여기서 인접한 배추들은 모두 방문처리
  print(worm)
 
  

 

github.com/HoYoungChun/Algorithm_PS/blob/master/DFS%26BFS/BOJ_1012.py

HoYoungChun/Algorithm_PS

 

※ 두번쨰 풀이 소스코드

 

DFS, BFS로 둘 다 그래프 탐색이 가능하므로 두 가지 함수를 모두 구현했습니다.

 

from collections import deque #큐 쓰기위해
import sys
sys.setrecursionlimit(10**6) #dfs에서의 재귀 깊이 늘리기위해

dx=[0,0,1,-1]
dy=[1,-1,0,0] #상하좌우 for문 위해

def bfs(q):
  while q:
    now_pop=q.popleft()
    now_x=now_pop[0]
    now_y=now_pop[1] #큐에서 뽑은거의 x,y좌표
    
    for i in range(4):
      new_x=now_x+dx[i]
      new_y=now_y+dy[i]
      if (0<=new_x<M) and (0<=new_y<N): #범위안에 있고
        if (maps[new_x][new_y]==1) and (not visited[new_x][new_y]): #1이고 방문X일때
          visited[new_x][new_y]=True #방문처리
          q.append([new_x,new_y]) #큐에 넣기

def dfs(now_x,now_y):
  visited[now_x][now_y]=True
  for i in range(4):
      new_x=now_x+dx[i]
      new_y=now_y+dy[i]
      if (0<=new_x<M) and (0<=new_y<N): #범위안에 있고
        if (maps[new_x][new_y]==1) and (not visited[new_x][new_y]): #1이고 방문X일때
          dfs(new_x,new_y)


T=int(input()) #테스트케이스
for _ in range(T):
  M,N,K=map(int,input().split())
  maps=[[0]*N for _ in range(M)] #배추밭
  visited= [[False]*N for _ in range(M)] #방문여부

  for _ in range(K):
    x,y=map(int,input().split())
    maps[x][y]=1 #배추있는 곳 1로
  
  jirung_count=0 #필요한 지렁이수 저장할 변수

  for i in range(M):
    for j in range(N):
      if maps[i][j]==1 and not visited[i][j]: #배추있고 방문안한곳일때
        jirung_count+=1 #필요한 지렁이수 1증가
        #visited[i][j]=True
        #q=deque([[i,j]])
        #bfs(q) #★경로있는 1들 모두 방문처리
        dfs(i,j)
  
  print(jirung_count)

github.com/HoYoungChun/Algorithm_PS/blob/master/DFS&BFS/BOJ_1012_2.py

HoYoungChun/Algorithm_PS