Algorithm475 [파이썬] 백준 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. [파이썬] 백준 1035 : 조각 움직이기 (골드1) [파이썬] 백준 1035 : 조각 움직이기 (골드1) 1035번: 조각 움직이기 최대 5개의 조각이 있는 5×5 크기의 보드가 있다. 김지민은 조각을 적절히 움직여서 모든 조각이 연결 요소를 이루게 하려고 한다. 즉 상하좌우로 인접한 조각을 모두 연결했을 때, 모든 쌍의 조 www.acmicpc.net 문제 풀이 0. 방향성 생각 array 상태가 * . 두개만 존재 + 5*5 : 2^25 -> bitmask 조각이 상태를 int로 변환해준 후, bitmask로 연산을 줄여준다. list로 변환하지 않고 bitstream을 이용해주면 더 빨리 풀 수 있지만, TLE안나고 충분히 가능할거라 생각해서 현재 상태를 2차원 array로 바꿔서 연결요소 개수를 체크한다. 1. 입력 from collections .. 2023. 12. 16. 이전 1 ··· 62 63 64 65 66 67 68 ··· 119 다음
