Algorithm/Graph188 [파이썬] 백준 5719 : 거의 최단 경로 (플레5) [파이썬] 백준 5719 : 거의 최단 경로 (플레5) 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 문제 풀이 0. 방향성 생각 다익스트라를 돌려서 end node에 최소 비용으로 도달하는 경우를 찾고, 이 노드들이 어디서 오는지 체크한다. 체크를 위해서 trace 변수를 넣어서 각 node로 들어오는 node가 어떤 노드인지 기록한다. trace를 이용해서 node를 최단 경로 노드들을 모두 shortcut에 넣는다. 다익스트라를 한 번 더 돌려서 end node에 도달할 .. 2023. 12. 19. [파이썬] 백준 2021 : 최소 환승 경로 (골드2) [파이썬] 백준 2021 : 최소 환승 경로 (골드2) 2021번: 최소 환승 경로 첫째 줄에 역의 개수 N(1≤N≤100,000), 노선의 개수 L(1≤L≤100,000)이 주어진다. 다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며 각 줄의 마지막에는 -1이 주어진다. 마지막 줄에는 출발 www.acmicpc.net 문제 풀이 0. 방향성 생각 필요한 노드는 환승역, 출발점, 시작점이다. 지나는 역의 개수가 2개 이상인 점과 출발점, 시작점만을 추출한다. BFS를 통해 탐색하고, 이동하면서 노선이 바뀌면 체크해주기 1. 입력 from collections import deque,defaultdict import sys input = lambda : sys.stdin.readline().rs.. 2023. 12. 17. [파이썬] 백준 5213 : 과외맨 (골드2) [파이썬] 백준 5213 : 과외맨 (골드2) 5213번: 과외맨 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 500) 다음 줄부터 N*N-N/2줄(/는 정수 나눗셈이다)에는 두 양의 Ai와 Bi가 주어진다. (1 ≤ Ai, Bi ≤ 6, 1 ≤ i ≤ N * N - N / 2) 타일 i의 왼쪽에 쓰여 있는 숫자는 Ai, 오른 www.acmicpc.net 문제 풀이 0. 방향성 생각 타일 넘버링을 잘 하기. 역추적을 해야한다.역추적 배열을 하나 더 만들어서 새로 갱신하는 경우에 온 경로에 이전 좌표를 갱신. 1. array 만들기 from collections import deque import sys input = lambda : sys.stdin.readline().rstrip() arr = [] n .. 2023. 12. 17. [파이썬] 백준 16441 : 아기돼지와 늑대 (골드3) [파이썬] 백준 16441 : 아기돼지와 늑대 (골드3) 16441번: 아기돼지와 늑대 첫 번째 줄에는 격자의 행의 수를 나타내는 N (3 ≤ N ≤ 100) 과 격자의 열의 수를 나타내는 M (3 ≤ M ≤ 100) 이 주어집니다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열 www.acmicpc.net 문제 풀이 0. 방향성 생각 빙판이 들어가는 방향마다 이동경로가 다르게 처리된다. 같은 빙판에 접근하더라도 들어가는 방향에 따라 다를 수 있기 때문에, 좌표에 대해서 방문처리하면 다른 방향으로 못갈 수도 있다. visit 좌표 위치에 4방향을 넣어서 방문체크를 한다. 1. 입력 from collections import deque import sys input = lambda.. 2023. 12. 17. 이전 1 ··· 26 27 28 29 30 31 32 ··· 47 다음
