Reenact

이진법으로 나타낸 각 수들 사이를 택시거리로 변환해서 BFS를 돌리면 된다. 여기서 주목할 점은 각 정수의 이진법 한자리를 바꿀 때 XOR을 이용한다는 것이다. 링크 : http://boj.kr/df7a494cc41e4bbead73ef81e0fd38f4

플레5 BFS인데 아이디어 자체는 골드 상위권 BFS 문제들보다 쉬웠다. 근데 구현에서 너무 오류를 많이 해서 7번만에 겨우 풀었다 대충 아이디어를 설명하자면 우선 백조들이 갈 수 있는 땅을 BFS로 구해서 vis에 기록해놓는다. 이 때 백조 종류에 따라 수를 다르게 기록해놓는다. 0은 두 백조 모두 방문안한 곳, 1은 첫번째 백조가 방문, 2는 두번째 백조가 방문한 곳으로 기록한다. 백조 BFS를 돌릴 때 사용하는 queue는 q다. 그 이후 물에 대한 BFS를 돌려서 물의 영역을 확장한다. 이 때 정확히 1번만 BFS를 돌려야 한다.(물의 영역 거리가 딱 1만큼만 늘어나도록) 그렇기 때문에 추가되는 점들을 wq1이라는 queue에 추가해야한다.(왜냐면 같은 queue에 추가해버리면 끝이 안나기 때문에..

이것도 불켜기랑 방식이 비슷하다. 우선 BFS를 돌려서 갈 수 있는 모든 곳을 탐색하고, 새로 얻은 key들을 보면서 그 key들로 열 수 있는 곳이면서 갈 수 있었던 지역과 바로 인접한 문들을 queue에 추가하고 또 BFS를 돌려 갈 수 있는 영역을 확장한다.

아이디어를 대략적으로 말하면 이렇다. 우선 현재 켜져있는 곳 중에서 갈 수 있는 모든 곳을 BFS를 돌려서 찾고 갈 수 있는 곳에서 모든 스위치들도 다 켜준다. 그 이후 새로 켜진 곳에 대해서, BFS로 방문한 곳과 연결되어있는 경우 그 켜진 곳을 queue에 포함시키고 다시 BFS를 추가로 돌려준다. 이런 식으로 새로 켜진 곳이 현재까지 방문한 지점과 연결되어있는 경우 queue에 추가해 다시 새로운 BFS를 돌려주는 방식으로 진행하였다. 그러면 O(N^2)로 문제를 해결할 수 있다.

now에 각 톱니바퀴의 현재 12시 방향에 있는 index를 저장해두었다.

구현 문제인데 그렇게 어렵진 않은 문제였다.. 근데 뭔가 코드를 깔끔하게 쓰고 싶은데 그러지 못해서 아쉬웠다

arr[i][j]가 i번째 수부터 j번째 수까지 부분수열에 대해 펠린드롬에 필요한 개수라고 정의하고 dp로 풀면 된다

DP문제라 점화식을 잘 세우면 어렵지 않게 풀린다.

다른 숨바꼭질과 다르게 최단거리로만 풀 수가 없었다. 동생을 먼저 이동시켜놓고 그다음 수빈이의 위치를 이동시켰다. 이 때 동생이 위치할 수 있는 좌표 중에 수빈이가 도달할 수 있는 최단 거리가 더 커지면 절대 동생을 그 위치에서 잡을 수 없다. 또 동생이 t초 후에 어떤 좌표에 있을 때 수빈이가 그 지점에 t보다 작으면서 t의 홀짝이 같도록 도착할 수 있으면 그 위치에서 동생을 잡을 수 있다.(같은 위치에서 1 -1을 반복해서 이동하면 되니) 이런 식으로 수빈이가 각 지점에 도착하는 최단시간을 홀수와 짝수로 나눠서 고려하였다. 그러면 O(n)이 걸린다.

기존의 벽 부수고 이동하기 문제와 비슷한데, 낮과 밤을 구분해주는 index를 추가해서 4차원 배열로 만들어주면 된다.