본문 바로가기
728x90

DFS37

[python] 백준 2250 트리의 높이와 너비 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 문제해결 중위 순회(incoder)(왼쪽 하위트리 → 루트 → 오른쪽 하위 트리 방향) 방식으로 보며 되며 그 순서를 x축에 표현한 것으로서 num이라는 변수로 표현하였으며 그 때의 깊이(level)을 index로 하여 row리스트에 저장을 한다.(append) row리스트에 모든 로드를 저장한 후 level=1부터 level=n까지 각 레벨에서 최대 x축(num)값을 가진 노드.. 2023. 2. 1.
[python] 백준 16964 DFS 스페셜 저지 https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 문제 해결 DFS와 BFS를 같이 쓰는 문제 입력 값을 하나씩 뽑아서 연결된 간선이 있을 때 다음 입력값과 같은 것이 있으면 계속 dfs를 이어 나간다. 끝까지 입력값을 이어나갈 수 있으면 1을 출력 그 전에 dfs가 끝나버리면 0을 출력 CODE import sys input = sys.stdin.readline from collections import de.. 2023. 1. 27.
[Python] 백준 16947 서울 지하철 2호선 https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 문제 해결 각 점(역)이 cycle 안에 들어가는지 확인해야한다. 이는 DFS를 통해 한바퀴 돌아 다시 출발한 점으로 올 수 있는지 확인한다. 2호선은 순환선이 한 개이지만 문제에서는 두개일 수도 있고 알 수 없다. 그래서 한번 사이클 만들었다고 끝이 아닐 수 있다. (모든 점에서 사이클을 돌려서 안에 있는지 확인해야한다는 점이다.) cycle안에 있는 점은 거리가 0으.. 2023. 1. 24.
[python] 백준 16929 Two Dots https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 문제 해결 DFS를 이용하기 좋다고 생각되는 문제 Cycle을 만들면 되므로 시작점에서 출발하여 방문하지 않은 길로 가서 다시 시작점으로 돌아올 수 있으면 cycle이 만들어지므로 바로 print("Yes") 출력하고 exit()를 통해 코드 종료 시작점을 (0,0) 부터 (n-1,m-1) 까지 m*n 개를 모두 돌리는 것이 마음에 안들지만 다른 방법이 생각이 안난다...ㅜㅜ 시작점을 기.. 2023. 1. 23.
728x90