본문 바로가기
728x90

그래프64

[python] 백준 1261 알고스팟 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제해결 다익스트라 (bfs를 이용해 꼭지점간의 최소 거리 측정) 벽이 없는 곳은 벽을 깨지 않으므로 비용(cost)가 이전이랑 같다. 따라서 deque()의 왼쪽에 다시 넣는다. 벽을 부시면 비용(cost)를 추가 지불 해야하므로 deque()오른쪽에 넣는다. deque가 없어질 때 까지 반복한 후 m,n 까지 가는데 비용을 출력한다. CODE import sys from .. 2023. 1. 29.
[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] 백준 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