https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 다른 사람들의 풀이보다 시간복잡도가 뒤쳐지지만, TLE도 아니고 스스로 풀었으니까 만족한다 ㅋㅎ 우선 입력범위에 해당 하는 소수들은 모조리 골라준다. 그리고 bfs를 시작하여, 현재 기준이 되는 소수와 단 한자리만 다르면서 아직 방문하지 않은 '소수'를 큐에 넣고 탐색을 이어간다. 한마디로 소수 판정 + bfs 이다. import sys from collections import deque #sys.set..
https://www.acmicpc.net/problem/27211 27211번: 도넛 행성 준겸이는 $N \times M$칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 www.acmicpc.net 조금 지저분하게 푼 것 양해바랍니다,, 우선, 보드의 크기와 입력은 고정되어있으므로 선언해준 뒤 시작한다. 이때 10x10 이라고 무조건 2차원 배열로 만들 필요는 없다! 주사위는 +1 ~ +6까지 무조건 양의 방향으로만 증가하므로 1차원 배열로 선언해주어야 더 쉽게 풀 수 있다. 사다리와 뱀의 정보도 구별 지을 필요 없다. 어찌됐건 둘 다 만나면 다른 곳으로 이동하므로 하나의 리스트에..
https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 숨바꼭질 시리즈의 최종판이다. 이 문제는 다른 문제들과 달리, 동생의 위치에 포커싱을 맞춰야한다. (1초에는 1만큼 움직이고, 2초에는 2만큼 움직인다) (즉, 움직인 거리로 시간을 대체할 수 있다!) 만약 수빈이가 14초에 x라는 지점을 방문했다고 하자. 그런데 동생이 20초에 그 x지점을 방문했다. 그럼 수빈이와 동생은 20초만에 만날 수 있는 것이다. 라..
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 숨바꼭질1에 이은 문제이다. 숨바꼭질1은 최단경로를 찾아 루트부터 해당 노드까지의 거리(= 가장 빠른 시간)를 출력하고 바로 종료했다면, 이 문제는 큐가 빌 때 까지 모든 경우를 다 탐색해주면 된다. 물론, 가장 빠른 시간이 찾아지면 그보다 시간이 오래 걸리는 경로는 필요없으므로 트리가 한단계 더 깊어지면 멈춰준다. 이것은 약간의 트릭이다. 멈추지않고 찾아도 ..
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 간단한 bfs문제이다. 큐에는 방문하는 숫자정보와 누적 방문 횟수를 저장해주면 된다. 그리고 현재 방문하는 숫자 - 1, 숫자 + 1, 숫자 x 2를 방문해주면 된다. 총 3가지 경우에 대해 모두 방문해보는 것이다. #include using namespace std; typedef unsigned long long ull; int n,k,ans; queue q; boo..
https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 오랜만에 푼 bfs 문제이다. 보물의 위치가 정해져있지 않기 때문에, 브루트포스를 이용하여 보물의 위치를 정해주는 것이 필요하다. 모든 육지(L)에 대해 bfs 탐색을 진행해주는데, 첫번째 L에 대해 bfs 탐색을 하고 얻게 된 가장 긴 길이가 5라고 할 때, bfs함수는 5를 반환하고 ans 변수에 저장한다. 지도를 초기화해준뒤, 2번째로 만나는 L에 대해 bfs 탐색을 하고 얻게 된 가장 긴 길이..
