chldkato

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입 www.acmicpc.net (0,0)에서 (n-1,n-1)까지 도둑루피의 크기가 최소가 되는 경로를 다익스트라로 구한 후 잃는 루피 값을 출력 ..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호가 주어진다. www.acmicpc.net 거쳐야하는 두 개의 정점을 a, b라고 하면 시작 - a - b - 끝, 시작 - b - a -끝 두 케이스에 대한 경로를 다익스트라로 구하면 된다 그리고 발생할 수 있는 모든 케이스를 고려하여 출력이 제대로 나올 수..

https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때 www.acmicpc.net 다익스트라로 최단 시간에 해당하는 경로를 구한다 1. 끝점 까지 가는 최단 시간 경로를 구한다 2. 다시 시작점으로 돌아오는 최단 시간 경로..

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net 벽을 부수는 횟수를 가중치로 생각하여 다익스트라를 수행한다 목표값에 도달하였을 때의 부순 횟수를 출력하면 부순 벽의 최소값이 된다 from heapq import heappush, heappop import sys input = sys.stdin.readline INF = sys.maxsize dx = [1, -1, 0, 0]..

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net 1. 부술 수 있는 뿌요를 bfs로 구하여 모두 부순다. 이 때 더 이상 부술 수 없으면 연쇄한 횟수를 출력 뿌요를 부순 횟수에 관계없이 부수는 과정이 발생하면 연쇄는 무조건 한 번 증가한다 2. 부순 후 떨어질 수 있는 뿌요를 구한다 뿌요의 바로 아래에 . 이 있으면 떨어져야 하므로 다른 뿌요가 있거나 바닥에 닿을 때 까지 뿌요를 떨어뜨린다. 3. 다시 1번부터 과정을 반복 from collections import deque import sys input = sys.stdin.r..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다. 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼 www.acmicpc.net 트리의 끝 지점만을 저장한 후 bfs로 끝 지점 간의 길이를 구한 후 최대값을 구하였더니 시간초과가 떴다 1. root로부터의 모든 ..

https://www.acmicpc.net/problem/1963

https://www.acmicpc.net/problem/9019 9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경 www.acmicpc.net 1. 주어진 조건에 맞게 이동할 수 있도록 bfs 안의 조건문을 설계 2. 주어진 입력으로부터 조건에 맞게 bfs로 경로를 저장하며 이동..