[DFS] 백준_양치기 꿍

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

3187번: 양치기 꿍

사이클을 찾아야하는 문제이니 DFS를 사용했습니다.
어떤 범위(울티리 안, 미로 공간) 안에서 개수 찾는 문제는 DFS를 통해 구현하고, 최단거리(최단경로)를 구해야하는 문제는 BFS를 이용하여 구현하고 있습니다.

재귀적으로 구현하였는데, 이때 sys.setrecursionlimit 함수를 통해 재귀한도를 지정하지 않으면 런타임에러가 뜨니 주의하셔야 합니다!

DFS 구현 방식은 다음과 같습니다.

1. 방향벡터 지정하기. (대각선 이동이 불가하고, 상하좌우 한칸씩 이동이라는 제한이 있을 때)
2. 방문 리스트 생성하기
3. DFS 정의하기
   1. 현재 노드 방문처리
   2. 반복문을 돌며 상하좌우 방문
   3. 경우의 수에 따라 처리하기
   4. 문제에 따라 필요한 부분에 코드 추가 구현하기
4. DFS 탐색하기

제가 푼 코드는 다음과 같습니다.

#백준 3187 양치기 꿍
#DFS

import sys
input=sys.stdin.readline
# v는 늑대, k는 양, #는 울리리, .은 빈공간
sys.setrecursionlimit(100000)  #런타임에러방지

r,c=map(int,input().split())
fence=[]
for i in range(r):
  fence.append(list(input().strip()))

k=0
v=0

#1 방향벡터(상하좌우)
dx=[-1,1,0,0] 
dy=[0,0,1,-1]

#2 방문리스트
visited=[[False]*c for _ in range(r)]

#3 dfs 정의
def dfs(x,y):
  global k, v  # 전역 변수로 선언
  #(1) 현재노드 방문처리
  visited[x][y]=True

  #문제에서 주어진 코드 풀이 (위치 달라질 수 있음)
  if (fence[x][y]=='k'): #양 수
    k+=1
  elif (fence[x][y]=='v'): #늑 수
    v+=1

  #(2) 반복문을 돌며 현재노드에서 이동할 상하좌우 노드 탐색
  for i in range(4):
    nx=x+dx[i]
    ny=y+dy[i]
    #(3) 경우의 수
    #맵을 벗어나지 않는 경우
    if (0<=nx<r and 0<=ny<c):
      #방문하지 않은 경우
      if (visited[nx][ny]==False):
        #울타리를 벗어나는 경우
        if (fence[nx][ny]!='#'):
          #(4) 이동할 노드로 재귀
          dfs(nx,ny)

wolf=0
sheep=0
#4 탐색
for x in range(r):
  for y in range(c):
    if visited[x][y]==False: #방문하지않은 곳 탐색
      v=0 
      k=0
      dfs(x,y)
      if v>=k: #늑대가 양보다 많거나 같으면 양 모두 잡아 먹힘
        k=0
      elif k>v: #양이 늑대보다 많으면 늑대 모두 잡아 먹힘
        v=0
      sheep+=k
      wolf+=v
      #한 사이클(한 울타리) 탐색을 마쳤을 때, 양과 늑대를 세는 변수 k,v
      #모든 탐색을 마쳤을 때, 양과 늑대를 세는 변수 sheep, wolf
print(sheep, wolf)

나만의 DFS 문제 풀이법을 찾은 거 같아 기분이 좋다.

앞으로 DFS BFS 위주로 풀면서 완전히 나의 것으로 만들고 싶다

재귀한도 잊지말기!