Junnnho

BOJ : https://www.acmicpc.net/problem/13549

github : https://github.com/junho0956/Algorithm/blob/master/13549/13549/%EC%86%8C%EC%8A%A4.cpp

숨바꼭질 문제 자체를 BFS 로 접근해야 하는 이유를 정확히 파악해보자면

가장 작은 간선(횟수)들로만 계속해서 연결해나가야 하기 때문에

현재 사용할 주어진 간선의 가중치가 동일하다는 전제조건이 있는 BFS 를 사용해야한다. 입니다

숨바꼭질3을 queue를 이용한 단순한 BFS 로 해결할 수 있을까? 에 대한 질문이 있다면

이 문제 자체는 문제의 특성 때문에 조건문만 잘 써준다면 우연히도 맞출 수 있게 됩니다.

그 우연한 조건이 *2 를 하고나서 +1 -1 순서로 queue 에 넣는것이 아닌 -1 +1 순서로 queue에 넣는 이유입니다.

어떤 경우에 +1 -1 이 오답처리가 되는지는 잘 모르겠습니다.

숨바꼭질3 같은 경우 *2 를 할때 간선(횟수)의 가중치가 0이 되게 됩니다.

BFS 를 하게 되면 다음으로 큰 가중치를 가진 간선을 push 하면서 맨뒤로 보내게 되는 과정을 알고 계실겁니다.

하지만 가중치가 0인 간선을 queue의 맨뒤로 보내면 이건 BFS 라고 할 수 없게 됩니다.

이 조건을 이용한다면 문제를 해결할 수 있게 됩니다.

가중치가 0인 간선을 queue의 back 이 아닌 front에 삽입할려면

list 형태의 queue 인 deque 를 이용하여 문제를 해결할 수 있게 됩니다.

BOJ : https://www.acmicpc.net/problem/12851

github : https://github.com/junho0956/Algorithm/blob/master/12851/12851/%EC%86%8C%EC%8A%A4.cpp

이 문제를 해결할 수 있는 방법은 2가지가 있을 것 같습니다.

1. 가장 정확한 방법

숨바꼭질(1697번) 문제를 생각해보면

큐에서 넣는 3가지 작업을 거치기 전에 방문배열을 확인해서 이미 방문했으면 패스하는 조건을 쓰게 됩니다.

하지만 이 경우 임의의 수가 *2, +1, -1 의 작업을 했을 때 같은 값을 가지게 된다면?

한가지 조건만 사용하게 되고 나머지는 사용하지 않게 될 것입니다.

숨바꼭질2 의 중요포인트는 이 부분이고, 이 부분을 해결하기 위해서는

큐에서 꺼낸 후에 pop 을 하면서 방문처리를 해주는 것+방문확인은 안하는 것 입니다.

좀더 정확히 말하자면 지금 사용할 값을 바로 방문처리 해주는 것입니다.

예를 들면 1->4 를 만들기 위해서는 

1 -> 2(+1) -> 4

1 -> 2(*2) -> 4

이 2가지 방법을 사용해야하고,

만약 큐에서 2를 꺼냈는데 방문을 확인해버리게 되면 +1 또는 *2 중 1개를 확인하게 되고

다음 큐에서 2를 꺼냈을 때는 방문한 것으로 확인하고 넘어가버리게 되서 나머지 1개를 확인하지 못하게 됩니다.

그러므로 2를 꺼내서 바로 방문처리를 해주고 확인은 하지않는다면? 

=> 2(+1)을 먼저 꺼냈다고 해도 큐에는 아직 2(*2) 가 남아있고

다음에 2(*2) 를 꺼내도 이미 방문은 했지만 확인은 하지 않으니 2(*2) 도 사용할 수 있게 되는 것입니다.

2. 편법을 통해서.. 문제를 해결할 수 있습니다.

애초에 어떤 임의의 수를 만들 수 있는 방법은 *2, +1, -1 이 있으니

아무리 많아도 3가지 일 것입니다.

방문배열을 체크만 하는 것이 아닌, 몆번 방문했는지 확인한다면

3번 을 초과해서 방문할 일은 없어집니다.

if (visit[now] > 3) continue;

visit[now]++;

의 코드를 사용한다면.. 1번 방법을 모르더라도 10만정도의 범위를 해결하는데는 무리가 없습니다 ㅎㅎ...

BOJ : https://www.acmicpc.net/problem/1697

github : https://github.com/junho0956/Algorithm/blob/master/1697/1697/%EC%86%8C%EC%8A%A4.cpp

숨바꼭질 같은 경우의 문제는

DFS 보다는 BFS 를 통해서 문제를 해결하여야 합니다.

방문처리를 확인해주는 것은 필수이고, +1 -1 *2 의 순서를 어떻게 줘야할지 고민했는데

*2 같은 값의 변화가 큰 것 부터 주는 것이 맞다고 생각해서 아래와 같이 구현하였고

처음에 생각했던 것은 queue 로부터 가장 먼저 발견됬다고 해도

이게 가장 적은 횟수일 보장이 있을까 하는 생각에 저런식으로 구현하였는데

포스팅을 하면서 생각해보니 now == K 가 성립되는 것은

가장 먼저 발견된 것이니 애초에 나머지 큐에 있는 것이 현재 cnt 보다 적을수가 없다는게 성립되고,

continue 가 아니라 break; 를 해주시는게 시간상 빠를 것 같습니다.

BOJ : https://www.acmicpc.net/problem/10819

github : https://github.com/junho0956/Algorithm/blob/master/10819/10819/%EC%86%8C%EC%8A%A4.cpp

완전탐색으로 가능한 모든 경우를 탐색하였으며

범위가 작아서 그런지 빠른 시간내로 해결했습니다.

탐색간 배열을 계속 만들어주어서 수를 확인하고 수가 없다면 삽입 후 넘기는 방식으로 코드하였습니다.

next_permutation (조합) 으로 구할 수 있지만 

아직 사용법과 내부 구현을 몰라서 공부 후에 적용해보겠습니다.