DFS

[문제] https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net [풀이] 약간.. 구현문제에 DFS 살짝 추가한 정도의 문제 같다. 그냥 7가지 경우의 수에 따라 파이프의 한쪽 끝이 원하는 위치에 도달할 때까지 깊이 우선 탐색을 진행한다. 아래 5가지에 유의하면서 풀었다. 1. 파이프 끝점을 기준으로 한다. 2. 파이프 주위 꼭 빈칸이어야 하는 곳에 벽이 있을 경우 파이프를 이동할 수 없다. 3. 파이프가 가로일 경우, 가로로..

[문제] https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net [풀이] 이 문제는 1) 사이클이 발생하는 구간을 구할 수 있는지, 2) 그래프 탐색으로 최단 거리를 구할 수 있는지 를 판단하는 문제이다. 따라서 아래와 같은 순서로 문제를 풀었다. 1. DFS 탐색을 통해 사이클이 발생하는 구간을 체크한다. 2. BFS 탐색을 통해 모든 노드에서 사이클이 발생하는 노드까지의 최단 거리를 계산한다. 1️⃣ 사이클 발생 구간 체..

[문제] https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net [풀이] 딱봐도 탐색문제..~ 내가 계속 BFS로 풀어서 DFS로도 한번 풀어봤다 계속 까먹어서 적어두는데 BFS는 deque를 이용해 풀고 DFS는 재귀 호출을 이용해 푼다. 공통점은 둘 다 visited를 이용해서 해당 칸 방문 여부를 검사했다. [BFS 코드] import sys from collections import deque n = int(sys.stdin.readli..

[문제] https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net [풀이] 🔥 DFS vs BFS ✨ DFS, BFS 모두 적합한 유형 단순히 모든 정점을 방문하는 것이 중요한 문제인 경우 ✨ DFS가 적합한 유형 검색 대상 그래프가 큰 경우 (정점과 간선의 개수가 많음) 경로의 특징을 저장해둬야 하는 문제 ex) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는 데 경로에 같은 숫자가 있으면 안된다는 문제 BFS는 경로의 특징을 가지지 못함 ..