본문 바로가기
728x90

그래프64

[python] 백준 1726 로봇 https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 문제 해결 BFS를 이용해서 새로운 길을 가면서 최소 거리를 찾는 것은 쉽게 알 수 있다. 그러나 방향을 좌, 우로 90도만큼 트는 것을 생각해야하고 직선으로 1칸부터 3칸까지 갈 수 있다는 것을 생각해야한다. visited에 바라보는 방향까지 포함시켜서 3차원 리스트로 저장을 하도록 한다. 회전은 90도만 가능하므로 동,서일 때는 남,북으로 회전 가능하고 남,북일 대는 동,서 방향으로 회전 가능하다. 중간.. 2023. 11. 22.
[python] 백준 1039 교환 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 숫자 안에 서로 다른 두개의 자릿수의 숫자를 바꿔가며 K번 바꾸었을 때 가장 큰 수를 만들 경우를 찾는 문제이다. 따라서 처음에 두 자릿수의 숫자를 바꿔서 가장 큰 수가 나왔다고 K번 바꾸었을 때 가장 큰 수가 만들어진다고 할 수 없다. 즉 거의 모든 경우의 수를 다 계산해야한다. 하지만 예외가 있다. 만약 한 자리의 자릿수가 가장 큰 자릿수, 즉 맨 왼쪽에 있는 수이고 나머지 하나의 자릿 수가 0일 경우 총 숫자의 자리수가 줄어들게 된다. 이런 경우는 예.. 2023. 11. 14.
[python] 백준 3584 가장 가까운 공통 조상 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 문제 해결 LCA (Low Common Ancestor)알고리즘 최소 공통 조상을 찾는 알고리즘은 트리문제에서 자주나오는 문제이다. 무조건 공통 조상은 있으므로 각 노드에서 루트로 올라가는 길을 정리하여 루트부터 다시 내려가면서 서로 갈라지는 지점을 찾으면 된다. 갈라지기 전에 가장 가까운 공통 조상이다! CODE import sys input .. 2023. 11. 13.
[python] 백준 12851 숨박꼭질 2 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 해결 가장 빠르게 N에서 K로 가는 길을 찾으면 된다. 이 때는 BFS를 이용하는 것이 좋다. 이동 했는데 이미 방문한 적이 있으면 더 빠르게 이동 할 수 있는 방법이 존재하는 것이므로 pass한다. ways를 통해 이동할 수 있는 방법이 여러개면 여러개가 있다는 것을 value 값을 통해 더해주면서 이동할 수 있다. CODE from collection.. 2023. 11. 1.
728x90