깊이 우선 탐색(DFS)은 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 통하는 간선이
있다면 그 간선을 방문하고, 이 과정에서 더 이상 방문할 곳이 없다면, 마지막에 방문했던 간선을 따라 뒤로 돌아가는 방
식이다. 동굴을 탐험한다고 생각하면 쉽다.
마지막에 방문했던 곳으로 되돌아간다는 점에서 스택과 비슷해서 그런지, DFS는 스택 또는 재귀 함수로 구현할 수 있다.
아래 코드는 DFS코드 예시이다.
DFS 경로 탐색(인접 리스트, 1260번 DFS와 BFS)
def dfs(node):
if check[node] == 0:
print(node, end=' ')
check[node] = 1
for n in sorted(li[node]):
dfs(n)
N, M, V = map(int, input().split())
li = [[] for _ in range(N+1)]
for _ in range(M):
a, b = map(int, input().split())
li[a].append(b)
li[b].append(a)
check = [0]*(N+1)
dfs(V)
print()
DFS 문제 풀이(인접 행렬, 1012번 유기농 배추)
import sys
sys.setrecursionlimit(10000)
def dfs(y, x):
graph[y][x] = 0
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for dy, dx in d:
Y, X = y+dy, x+dx
if (0 <= Y < N) and (0 <= X < M) and graph[Y][X] == 1:
dfs(Y, X)
for case in range(int(input())):
M, N, K = map(int, input().split())
graph = [[0]*M for _ in range(N)]
for _ in range(K):
x, y = map(int, input().split())
graph[y][x] = 1
res = 0
for i in range(N):
for j in range(M):
if graph[i][j] == 1:
dfs(i, j)
res += 1
print(res)
백준 알고리즘 문제 풀이)
백준 알고리즘 1012번 유기농 배추(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(10000) def dfs(y, x): graph[y][x] = 0 d = [(-1, 0), (1, 0), (0, -1), (0, 1)] for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < N)..
jinho-study.tistory.com
백준 알고리즘 1260번 DFS와 BFS(python)
기본적인 DFS & BFS 문제이다. from collections import deque def dfs(node): if check[node] == 0: print(node, end=' ') check[node] = 1 for n in sorted(li[node]): dfs(n) def bfs(start): queue = deque([s..
jinho-study.tistory.com
백준 알고리즘 2606번 바이러스(python)
기본적인 DFS & BFS 문제이다. 양방향임 구조임에 주의하자. 처음에 단방향으로 만들어 놓고 풀려해서 왜 틀렸는지 한참을 찾았다. DFS 풀이 def dfs(node): if check[node] == 0: check[node] = 1 for t in graph..
jinho-study.tistory.com
백준 알고리즘 2667번 단지번호붙이기(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 def dfs(y, x, cnt): graph[y][x] = 0 d = [(-1, 0), (0, 1), (1, 0), (0, -1)] for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < N) and (0 <= X < N) and graph[Y][X] =..
jinho-study.tistory.com
백준 알고리즘 1743번 음식물 피하기(python)
DFS & BFS 문제이다. BFS 풀이 from collections import deque def bfs(i, j): queue = deque() queue.append((i, j)) d = [(-1, 0), (1, 0), (0, -1), (0, 1)] cnt = 1 while queue: y, x = queue.popleft() for..
jinho-study.tistory.com
백준 알고리즘 2468번 안전 영역(python)
DFS & BFS 문제이다. BFS는 큐에 넣을 때 방문 표시를 해줘야 된다는 점을 항상 주의해야겠다. 큐에서 뺀 뒤에 하면 같은 좌표가 중복으로 큐에 들어가는 것이 반복된다. DFS 풀이 import sys from copy impor
jinho-study.tistory.com
백준 알고리즘 2583번 영역 구하기(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(10000) def dfs(y, x, cnt): graph[y][x] = 1 for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < M) and (0 <= X < N) and graph[Y][X]..
jinho-study.tistory.com
백준 알고리즘 4963번 섬의 개수(python)
DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(10000) def dfs(y, x): graph[y][x] = 0 for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < h) and (0 <= X < w) and graph[Y][X] == 1: dfs(Y, X..
jinho-study.tistory.com
백준 알고리즘 11724번 연결 요소의 개수(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(10000) def dfs(node): check[node] = 1 for n in graph[node]: if check[n] == 0: dfs(n) N, M = map(int, sys.stdin.readline().split..
jinho-study.tistory.com
백준 알고리즘 10026번 적록색약(python)
DFS & BFS 문제이다. 나름 짧게 잘 구현한 것 같다. 이제 좀 DFS, BFS에 익숙해진 것 같다!! DFS 풀이 import sys from copy import deepcopy sys.setrecursionlimit(10000) def dfs(y, x, color): t[y][x] = '0'..
jinho-study.tistory.com
백준 알고리즘 11725번 트리의 부모 찾기(python)
트리 & DFS & BFS 문제이다. 시간 초과를 매우 조심해야 되는 문제다. 처음에 방문 체크 리스트를 N-2번 생성하고 순서대로 체크하도록 구현했어서 그런지 시간 초과가 엄청 나왔다. DFS 풀이 import sys
jinho-study.tistory.com
백준 알고리즘 2644번 촌수계산(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(300000) def dfs(node): for n in graph[node]: if check[n] == 0: check[n] = check[node]+1 dfs(n) n = int(input()) graph = [[] for..
jinho-study.tistory.com
백준 알고리즘 11558번 The Game of Death(python)
간단한 그래프 탐색 문제이다. 그냥 DFS 방식으로 풀었다. def dfs(node): for n in graph[node]: if check[n] == 0: check[n] = check[node]+1 dfs(n) for _ in range(int(input())): N = int(input()) graph = [..
jinho-study.tistory.com
백준 알고리즘 11559번 Puyo Puyo(python)
구현 & DFS & BFS 문제이다. 기업 코딩 테스트에서 나올 것 같은 문제인데 참 재밌게 푼 것 같다. 1. 터트릴 뿌요가 있는지 확인하는 함수(같은 색깔의 뿌요가 4개 이상 뭉쳐 있는지 확인) 2. 뿌요를
jinho-study.tistory.com
백준 알고리즘 9372번 상근이의 여행(python)
트리 & 그래프 이론 문제이다. 문제가 웃긴게 애초에 모든 국가가 연결되있기 때문에 N-1을 출력해면 끝이다. 처음에는 이걸 생각 못해서 두 번째 코드 같ㅇ탐색해서 풀었다. for _ in range(int(input())
jinho-study.tistory.com
다시 풀자_백준 알고리즘 9205번 맥주 마시면서 걸어가기(python)
BFS & DFS 문제이다. 인접리스트를 행렬 형식으로 구현해서 그래프를 생성하면 쉽게 풀 수 있다. 이걸 생각못해서 1시간 넘게 뻘짓을 했다. BFS 풀이 from collections import deque def make_graph(): for i in r..
jinho-study.tistory.com
백준 알고리즘 13565번 침투(python)
기본적인 DFS & BFS 문제이다. 첫번째 줄만 탐색을 시킨 후에 마지막 줄이 탐색이 된 적 있으면 "YES" 아니면 "NO"를 출력해주면 된다. DFS 풀이 import sys sys.setrecursionlimit(3000000) def dfs(y, x): graph..
jinho-study.tistory.com
백준 알고리즘 3187번 양치기 꿍(python)
기본적인 DFS & BFS 문제이다. 3184번 양과 거의 동일한 문제이다. 그냥 BFS으로만 풀었다. BFS 풀이 from collections import deque def bfs(y, x): queue = deque() queue.append((y, x)) s = w = 0 while queue..
jinho-study.tistory.com
백준 알고리즘 14716번 현수막(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(3000000) def dfs(y, x): graph[y][x] = 0 for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < M) and (0 <= X < N) and graph[Y][X] ==..
jinho-study.tistory.com
백준 알고리즘 1303번 전쟁 - 전투(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(3000000) def dfs(y, x, cnt): c = graph[y][x] graph[y][x] = 1 for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < M) and (0 <= X < N..
jinho-study.tistory.com
백준 알고리즘 11123번 양 한마리... 양 두마리...(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(3000000) def dfs(y, x): graph[y][x] = '.' for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < H) and (0 <= X < W) and graph[Y][X] =..
jinho-study.tistory.com
백준 알고리즘 4677번 Oil Deposits(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(3000000) def dfs(y, x): graph[y][x] = '*' for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < m) and (0 <= X < n) and graph[Y][X] =..
jinho-study.tistory.com
백준 알고리즘 15240번 Paint bucket(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(3000000) def dfs(y, x, K, n): graph[y][x] = K for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < R) and (0 <= X < C) and graph[Y][..
jinho-study.tistory.com
백준 알고리즘 15092번 Sheba’s Amoebas(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(3000000) def dfs(y, x): graph[y][x] = '.' for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < m) and (0 <= X < n) and graph[Y][X] =..
jinho-study.tistory.com
백준 알고리즘 5938번 Daisy Chains in the Field(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(3000000) def dfs(node): check[node] = 1 for n in graph[node]: if check[n] == 0: dfs(n) N, M = map(int, input().split()) graph =..
jinho-study.tistory.com
백준 알고리즘 2210번 숫자판 점프(python)
브루트포스 알고리즘 & DFS 문제이다. 문자열 s를 계속 업데이트하다가 길이가 6이면 set(res)에 추가해주고, 마지막에 set의 길이를 출력해주면 된다. import sys sys.setrecursionlimit(3000000) def dfs(y, x,..
jinho-study.tistory.com
백준 알고리즘 19621번 회의실 배정 2(python)
기본적인 DFS 문제이다. 현재 회의가 끝나는 시간이 제일 늦은 회의 시작 시간보다 크면 더 이상 회의를 할 수 없는 상황이므로 여태까지 회의에 참여한 인원수를 리스트에 추가해준다. 마지막에
jinho-study.tistory.com
백준 알고리즘 16390번 Sheba’s Amoebas(python)
기본적인 DFS & BFS 문제이다. 15092번 Sheba’s Amoebas와 같은 문제이다. DFS 풀이 import sys sys.setrecursionlimit(3000000) def dfs(y, x): graph[y][x] = '.' for dy, dx in d: Y, X = y+dy, x+dx if (0 <=..
jinho-study.tistory.com
백준 알고리즘 14145번 Žetva(python)
기본적인 DFS & BFS 문제이다. 처음에 그래프를 생성할 때 graph = [map(int, list(input())) for _ in range(R)] 와 같은 방식으로 생성해서 계속 메모리 초과가 나왔다. graph = [list(input()) for _ in range(..
jinho-study.tistory.com
https://jinho-study.tistory.com/1086
프로그래머스 Level 3 여행경로
리스트가 아닌 딕셔너리로 그래프를 구현해서 풀어야되는 문제이다. 올바른 경로를 찾을 때까지 뺑뺑이를 돌려줘야 되는 문제라 dfs로 풀었다. 핵심은 dfs 함수를 재귀로 넘기기 전에 딕셔너리의
jinho-study.tistory.com
https://jinho-study.tistory.com/1087
프로그래머스 Level 3 네트워크
간단한 그래프 탐색 문제이다. 반복문을 돌면서 체크가 안된 노드가 있다면 ans += 1을 하고 그 노드부터 시작하여 dfs 또는 bfs를 돌려서 갈 수 있는 길을 다 체크해주면 된다. check[i] = 0 -> i 노드 들
jinho-study.tistory.com
https://jinho-study.tistory.com/1088
프로그래머스 Level 3 단어 변환
begin에서 target으로 가는 최단경로의 길이를 찾는 문제이다. 두 단어의 차이가 한 글자면 이동 가능하다. 이동 가능한지 판별하는 부분은 아래의 조건문같이 구현했다. if len([1 for i in range(N) if node
jinho-study.tistory.com
https://jinho-study.tistory.com/1096
백준 알고리즘 3182번 한동이는 공부가 하기 싫어!(python)
기본적인 그래프 탐색 문제이다. 각 노드별로 몇 명의 사람을 만날 수 있는지 확인하고, 최댓값의 인덱스를 출력해주면 된다 -> res.index(max(res)) def dfs(node, cnt): check[node] = 1 n = graph[node][0] if..
jinho-study.tistory.com
https://jinho-study.tistory.com/1099
백준 알고리즘 16173번 점프왕 쩰리 (Small)(python)
기본적인 BFS, DFS 문제이다. (N, N) 좌표에 도착할 수 있는지를 확인해주면 된다. BFS 풀이 from collections import deque def bfs(y, x): q = deque() q.append((y, x, li[y][x])) while q: y, x, d = q.poplef..
jinho-study.tistory.com
'Agorithm > 자료구조, 알고리즘 정리' 카테고리의 다른 글
| 동적 계획법(Dynamic programming) (백준 문제 포함) (0) | 2021.03.17 |
|---|---|
| 너비 우선 탐색(breadth-first search, BFS) (백준 문제 포함) (0) | 2021.03.10 |
| 큐(Queue), 덱(Deque) (백준 문제 포함) (0) | 2021.03.05 |
| 스택(Stack) (백준 문제 포함) (0) | 2021.03.05 |
| 그리디(greedy) 알고리즘 (백준 문제 포함) (0) | 2021.01.29 |