백준 DFS 모음

DFS(Depth First Search, 깊이 우선 탐색)

시작 정점에서 한 방향으로 계속 탐색하다가 더 이상 갈 곳이 없으면 가장 마지막 분기 간선이 있는 정점으로 돌아와 다른 방향의 정점의 탐색을 반복해 모든 정점을 방문하는 순회 기법

스택을 사용해 구현한다.

 

파이썬으로 DFS를 구현할 때  주의

import sys
sys.setrecursionlimit(100000)

 

2583번 영역 구하기

2644번 촌수계산

16173번 점프왕 쩰리

1167번 트리의 지름

1937번 욕심쟁이 판다

9466번 텀 프로젝트

---

2583번 영역 구하기

import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline

m,n,k=map(int, input().split())
graph=[[0]*n for _ in range(m)]

# 입력받은 사각형 내부를 1로 표시
for _ in range(k):
    lx,ly,rx,ry=map(int, input().split())
    for i in range(m-ry,m-ly): 
        for j in range(lx,rx):
            graph[i][j]=1
            


dx=[-1,1,0,0]
dy=[0,0,-1,1]
def dfs(x,y):
    global count
    graph[x][y]=1 # 좌표를 1로 변경
    count+=1 # 내부 칸수 세기
    for i in range(4): # 상하좌우 탐색
        nx=x+dx[i]
        ny=y+dy[i]

        if 0<=nx<m and 0<=ny<n: # 범위 안에 든다
            if graph[nx][ny]==0: # 비어있다
                dfs(nx,ny) # 재귀
count=0 # 내부 넓이
area=[]
for i in range(m):
    for j in range(n):
        if graph[i][j]==0: # 비어있는 부분이면
            dfs(i,j) # 탐색을 한다
            area.append(count)
            count=0
print(len(area))
area.sort()
for i in area:
    print(i, end=' ')

 

 

2644번 촌수계산

import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline

n=int(input())
a,b=map(int, input().split()) # 구하고자 하는 두 사람의 번호 a->b 이동거리를 계산
m=int(input()) # 관계의 개수
graph=[[] for _ in range(n+1)]
for i in range(m):
    x,y=map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
visited=[0]*(n+1)

def dfs(v):
    for i in graph[v]: # 현재 노드에 연결된 노드들을 돌면서
        if visited[i]==0: # 연결된 노드들에 아직 방문을 안했으면
            visited[i]=visited[v]+1 # 촌수를 증가시키면서 저장
            dfs(i)   
dfs(a)
print(visited[b] if visited[b]>0 else -1)

 

 

16173번 점프왕 쩰리

import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline

n=int(input())
graph=[list(map(int,input().split())) for _ in range(n)]
visited=[[0]*n for _ in range(n)]


dx=[0,1] # 아래로 이동
dy=[1,0] # 오른쪽으로 이동
# 다음에 이동할 수 있는 칸을 저장해서 
def dfs(x,y):

    if graph[x][y]==-1 :# 마지막 지점에 도달했으면
        print("HaruHaru")
        exit(0)
    visited[x][y]=1
    c=graph[x][y] # 한번에 이동 가능한 거리

    for i in range(2):
        nx=x+dx[i]*c
        ny=y+dy[i]*c

        if 0<=nx<n and 0<=ny<n: # 맵의 범위를 벗어나지 않으면
            if visited[nx][ny]==0:
                visited[nx][ny]=1
                dfs(nx,ny)

    return False
    

if dfs(0,0)==False: # 출발 위치
    print("Hing")

 

 

1167번 트리의 지름

# 임의의 노드에서 가장 먼 노드를 구하고 이 노드를 a라고 한다
# a에서 가장 먼 노드를 구해서 b라고 한다.
# a와 b의 거리가 트리의 지름이다.
# => dfs를 두번사용

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

def dfs(v,dis):
    for x,y in graph[v]: #그래프에서 연결된 노드와 가중치를 가져옴
        if visited[x]==-1: # 연결된 노드가 방문하지 않은 곳이면
            visited[x]=dis+y # 가중치+ 그전의 가중치
            dfs(x,dis+y)

            
v=int(input()) # 정점의 개수

graph=[[] for _ in range(v+1)]
for i in range(v):
    x = list(map(int, input().split()))
    for j in range(1, len(x)-2, 2):
        graph[x[0]].append([x[j], x[j + 1]])

visited=[-1]*(v+1)
visited[1]=0

dfs(1,0) # 임의의 노드 1번에서 가장 먼 노드를 구한다.

start=visited.index(max(visited))
visited=[-1]*(v+1) # 다시 dfs로 탐색해야하므로 초기화
visited[start]=0
dfs(start,0)

print(max(visited))

 

 

1937번 욕심쟁이 판다

# dfs와 dp를 같이 이용해야 한다.

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

n=int(input())
graph=[list(map(int, input().split())) for i in range(n)]
dp = [[0] * n for _ in range(n)] # 현재 노드에서 dfs했을 때 최대 몇칸 이동인지 기록

dx=[0,0,-1,1]
dy=[-1,1,0,0]

def dfs(x,y):
    if dp[x][y]==0: # 방문한 적이 없으면
        dp[x][y]=1 # 1로 바꾼다
        
    else: # 방문한 적이 있으면 그대로 리턴
        return dp[x][y]
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if graph[x][y]<graph[nx][ny]: # 이동한 칸의 대나무가 더 많아야 한다
                dp[x][y]=max(dp[x][y], dfs(nx,ny)+1) # 현재 위치와 상하좌우 탐색을 했을 때 어떤 것이 더 최대인지
    return dp[x][y] # 현재 노드의 최대 이동 칸수를 리턴

result = 0
for i in range(n):
    for j in range(n):
        result = max(result, dfs(i, j))

print(result)

 

 

9466번 텀 프로젝트

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

def dfs(v):
    global cnt
    cycle.append(v) # 현재 사람을 싸이클에 추가
    visited[v]=1 # 방문체크
    next=graph[v] # v가 지목한 사람

    if visited[next]==1: # 지목당한 사람의 방문이 체크되어 있으면
        if next in cycle: # 이 사람이 싸이클에 포함되어 있으면
            cnt+=cycle[cycle.index(next):] # 싸이클이 시작된 사람부터 끝까지
        return
    else: # 지목당한 사람의 방문이 체크되어 있지 않으면
        dfs(next) # 그 사람이 지목한 사람으로 넘어간다



t= int(input()) # 테스트 케이스

for _ in range(t):
    n=int(input()) # 학생의 수
    graph=[0]+list(map(int, input().split()))
    visited=[0]*(n+1)
    cnt=[]

    for i in range(n+1):
        if visited[i]==0: # 방문한 적이 없으면
            cycle=[] # 싸이클 초기화
            dfs(i)
            
    print(n-len(cnt)+1) # 0 고려하기