Reenact

앞에서 한 1600번 말이 되고픈 원숭이 문제랑 거의 같다

BFS인데 previous point를 저장해놓는 배열을 추가로 해주면 된다

벽부수고 이동하기 문제랑 매우 유사하다 대신 벽부수고 이동하기는 벽을 최대 1번만 부셨는데 여기선 횟수 K를 입력으로 받아서 최대 K번까지 말 방식으로 이동할 수가 있다. 제출한 링크 : http://boj.kr/dfcb284cba4e411b9555874969aa3397

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 문제다!

그리디 아이디어와 multiset을 이용하면 간단하게 풀 수 있다. 근데 그리디 아이디어 자체를 떠올리는 건 쉬웠는데 이를 엄밀하게 증명하려고 하니 좀 까다로웠다

recommend, recommend3에서 lower bound를 적절히 이용해야돼서 set을 사용하였다. 근데 set 1개만으론 안될 것 같아서 g를 1순위로 sorting하는 glp, l을 1순위로 sorting하는 lp인 set 2개를 만들었다. 그리고 문제 번호는 유일하기 때문에 문제 번호를 key로, 난이도와 그룹번호 쌍을 value로 하는 map mp를 만들어서 p 1개에 대해 l와 g값을 바로 알 수 있도록 만들었다.