Reenact

BFS를 돌리면 되는 데 이때 다음 점을 넣는 과정에서 2를 계속 곱해줘서 최대한 많이 들어갈 수 있도록 큐에 넣어줘야 한다. 코드 : http://boj.kr/483dc81226554bd8b71b567111163dff

O(n^4)가 되는데 n이 다행히 100까지라서 돌아간다 n x n 에서 bfs를 돌리다가 한 섬을 찾으면, 그 섬에 대해 가장자리 위치들만 Q1에 push하고 거기서부터 BFS를 돌린다. 그러다가 다른 1에 도달하면 정답을 갱신하는 방식으로 풀 수 있다. 섬을 찾는 bfs의 Queue와 방문 array는 Q와 vis, 한 섬의 가장자리에서부터 다른 섬까지 bfs를 돌리는 것은 Q1과 vis1이다.

BFS문제라는데 BFS로 푼 거 같지가 않다...굳이 따지자면 지나온 점들을 체크하는 게 BFS랑 겹치는 부분이다 방문하지 않은 점들의 다음 점들을 확인해가면서, 다음점이 방문했던 점인 경우 2가지로 나눠 문제를 해결할 수 있다. 첫 번째는 다음 점(nx)이 이전 지나온 점들과 같은 경우 Cycle의 일부가 완성되므로 Cycle에 도달하기 전까지의 점들은 팀을 이룰 수 없는 것이라 그 전까지의 점의 개수를 더해준다. 두 번째로는 다음 점이 이전 지나온 점들과 다르면서 기존에 방문했던 점의 경우인데, 이 경우 지나온 점들 모두가 Cycle에 포함될 수가 없으니 팀을 이룰 수 없어서 지나온 점들을 모두 더해준다. vis를 -1로 초기화시키고 진행하므로 vis에 각 점들이 1번씩만 찍혀서 O(N)으로 문제를 ..

불에 대한 BFS를 먼저 구현하고 상근이의 BFS를 구현해주면 된다.

1차원 BFS 문제다!