[이코테] 3강. DFS&BFS 리뷰

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3

암기할 것

 

import sys
# 1. 재귀 깊이 한도 늘리기 (런타임 에러 해결)
sys.setrecursionlimit(10**6) 
# 2. 빠른 입력을 위해 input 함수를 sys.stdin.readline으로 변경
input = sys.stdin.readline

 

파이썬에서 2D 리스트는 graph[세로][가로] (즉, graph[row][col]) 순서로 접근하는 게 가장 편함

예를 들어 세로 3줄, 가로 5칸짜리 리스트를 만든다면, graph = [[0] * 5 for _ in range(3)] 이렇게 만들고, graph[1][3] (1번 세로줄의 3번 가로칸) 처럼 쓴다!

 

 

 

영상의 내용 순서

 

1.스택과 큐 자료구조

 

2.재귀함수

• 최대공약수 계산 (유클리드 호제법)

3.DFS(깊이 우선 탐색, 스택 자료구조 이용)

• 음료수 얼려먹기

4.BFS(너비 우선 탐색, 큐 자료구조 이용)

 

 

제미나이의 관련 추천 문제

1단계: DFS, BFS 둘 다 연습하기 (기본 중의 기본)

가장 기본적인 DFS, BFS 형태를 연습하는 문제입니다. 하나의 문제로 DFS로도 풀어보고, BFS로도 풀어보세요.

• (10월 24일 풀이 완료)BOJ 1260(실버2) - DFS와 BFS https://www.acmicpc.net/problem/1260
  • 이유: DFS와 BFS의 정석 코드를 연습하기에 가장 좋은 필수 문제입니다. '방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문'하라는 조건 때문에 정렬이 필요하지만, 기본 구조를 잡는 데 최고입니다.
  • 팁: 인접 리스트(파이썬에서는 list의 list)와 인접 행렬(2차원 배열) 두 가지 방식으로 모두 그래프를 표현하고 풀어보세요.

---

## 2단계: '덩어리' 세기 (DFS가 편한 문제)

'음료수 얼려먹기'와 거의 똑같은 유형입니다. 2차원 배열(격자)에서 상하좌우로 연결된 덩어리(Connected Component)를 찾는 문제입니다.

• (10월 24일 풀이 완료) BOJ 2606(실버 3) - 바이러스 https://www.acmicpc.net/problem/2606
  • 이유: 1번 컴퓨터와 "연결된" 모든 컴퓨터를 찾는 문제입니다. 1260번 문제와 비슷하지만, 덩어리 개수가 아닌 1번과 연결된 총 개수를 묻는 문제입니다. DFS 또는 BFS로 쉽게 풀 수 있습니다.
• (10월 28일 풀이 완료) BOJ 2667(실버1) - 단지번호붙이기 https://www.acmicpc.net/problem/2667
  • 이유: '음료수 얼려먹기'와 완전히 동일한 유형입니다. 1로 연결된 집들의 덩어리(단지)가 총 몇 개인지, 그리고 각 단지마다 집이 몇 채인지 세는 문제입니다. DFS로 각 덩어리를 탐색하면서 개수를 세면 됩니다.
• (10월 27일 풀이 완료 어렵다) BOJ 1012(실버2) - 유기농 배추 https://www.acmicpc.net/problem/1012
  • 이유: 이것도 '단지번호붙이기'와 똑같습니다. 배추(1)들이 모여있는 덩어리마다 지렁이(탐색)가 한 마리씩 필요합니다. 총 몇 덩어리인지(지렁이가 몇 마리 필요한지) 세는 문제입니다.

---

## 3단계: 최단 거리 (BFS가 필수인 문제)

'미로 탈출'과 똑같은 유형입니다. 2차원 배열에서 최단 거리를 찾는, BFS의 가장 전형적인 문제입니다.

• (10월 28일 풀이완료) BOJ 2178(실버1) - 미로 탐색 https://www.acmicpc.net/problem/2178
  • 이유: '미로 탈출' 문제와 완전히 동일한 유형입니다. (1, 1)에서 (N, M)까지 가는 최소 칸 수를 구하는 문제입니다. BFS를 사용해야 하는 이유를 확실하게 알 수 있는 문제입니다.
  • 팁: 방문 여부 배열(visited) 대신, 미로 배열 자체에 거리를 1, 2, 3... 순서대로 기록하면서 진행하면 편리합니다.
• (10월 29일 풀이완료) BOJ 7576(골드5) - 토마토 https://www.acmicpc.net/problem/7576
  • 이유: '미로 탐색'의 살짝 응용 버전입니다. 시작점이 하나가 아니라 여러 개(익은 토마토들)일 수 있습니다. 모든 토마토가 익는 데(모든 1로 퍼지는 데) 걸리는 최소 일수를 묻습니다. BFS 큐에 시작점(익은 토마토)들을 모두 넣고 시작하면 됩니다