본문 바로가기
728x90

BFS50

[python] 백준 2146 다리 만들기 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 문제 해결 섬을 어떻게 구별할 것인가? → 연결 되어 있는 섬을 1, 2, 3 ... 으로 카테고리별로 구분하도록 한다.(0은 바다) 섬끼리 거리를 어떻게 측정할 것인가? → 동, 서, 남, 북으로 이동시켜서 바다부분에서 거리를 +1씩 더한다음 출발점고 다른 새로운 카테고리 대륙이 나오면 이전의 기록된 최소 거리와 비교해서 최소거리를 ans로 저장을 한다. 이를 bfs를 통해서 계속 진행한다. CODE.. 2023. 1. 27.
[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] 백준 16940 BFS 스페셜 저지 https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 문제 해결 단순한 BFS 문제 + 순서가 여러가지 나올 수 있는 경우를 visited 리스트를 통해 체크해서 주어진 순서와 비교 chlldren 집합을 통해 그 순서에 나올 수 있는 경우를 모두 넣어 안에 들어있으면 pass 아니면 0을 출력하고 코드를 끝낸다. n까지 나열 한 것이므로 index=n까지 경우의 수 안에 들어 있으면 1을 출력한다. CODE import sys input = sys.stdin.readline from collections import deque n = int(input()) gra.. 2023. 1. 25.
[python] 백준 11724 연결 요소의 개수 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제 해결 그래프가 몇개로 분리되어있는지 개수를 세는 문제 visited 리스트를 통해 지나간 점을 체크하면서 1번부터 n번까지 dfs나 bfs를 돌리면서 몇번 돌려야 visited 리스트 원소가 모두 True가 되는지 count 한다고 생각하면 된다. CODE(dfs) import sys sys.setrecursionlimit(500.. 2023. 1. 22.
728x90