https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 숨바꼭질5는 수빈이 뿐만 아니라 동생도 움직인다. 동생이 고정되어있을 때는 고정된 한점으로 이동하는 최단 경로를 찾기 때문에 쉽게 문제를 풀 수 있다. 그렇지만 이번에는 동생도 동적으로 움직인다. 그렇다면 여기서 고려해야할 부분은 예전에 방문했던 부분을 다시 방문하지 않아도 되냐는 것이다. 결론은 예전에 방문했던 부분을 다시 방문해야한다는 것이다. 이전에는..
https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 처음에 문제를 잘못 이해했다. 원소가 중복되는 갯수가 K 이상인 경우로 경계 조건을 오인했다. 예를 들어 5 5 2 2 2라는 값이 들어오면, 중복되는 것이니 총 5개의 원소가 중복된다고 판단했다. 그런데 실제 문제는 약간 다르다. 중복되는 원소가 있는 경우, 중복된 원소들 중 최대 갯수가 K이상인 경우를 발라내는 것이었다. 예를 들어 5 5 2 2 2 라고 하면, 현재 중복된 값은 ..
https://www.acmicpc.net/problem/13913 숨바꼭질3에서 경로를 출력해야하는 문제다.경로를 출력하는 방법은 여러가지가 있다. que에 경로를 함께 기억한다. 경로 배열을 만들고, 각 배열에 올 수 있는 가장 빠른 경로를 업데이트 한다 이렇게 할 경우, 2번은 메모리 초과가 발생했다. 따라서 1번 방법으로 접근했다. 1번 방법으로 접근했을 때, 모든 경로를 숫자로 직접 입력해두었을 때 간단한 연산임에도 불구하고 어마어마한 시간이 필요했다. 돌이켜보면 10만개를 다 돌릴 수도 있는데, 10만개에 대한 주소를 모두 Path로 가지고 있다면 그 String을 넘겨주는 것과 메모리는 장난이 아닐꺼다. "100000 99999 99998 ... 1... 이렇게 온다고 생각해보면 ..
https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 수빈이는 움직이고, 동생은 움직이지 않는다. 따라서 수빈이가 움직이는 경우만 잘 처리해주면 된다. 기본적인 BFS 문제인데, 하나 조심해야할 부분은 순간이동을 하게 되면 이동하는데 필요한 시간이 0초라는 것이다. 따라서 순간이동하는 경우도 가장 뒷쪽으로 넣은 경우, 수빈이가 동생을 만나는 모든 경우의 수에 대해 최소값을 기록해야 정답이 된다. 반대로 Deque을 ..
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분 그래프가 어떤 그래프인지 문제에 있는 설명으로 알 수가 없어, 검색을 하고 풀었다.문제의 핵심은 전체 그래프가 2개의 그룹으로 나누어 질 수 있는지 보면 된다. 예를 들어 처음 탐색을 시작하는 그래프의 그룹을 1이라고 가정하면, 그 다음으로 탐색 되는 그래프의 그룹은 2가 된다. 그리고 그 다음으로 탐색 되는 그래프의 그룹은 1이 된다. 이 경우를 만족하는지를 판별하면 된다. 모든 노드에 대..