Closed changicho closed 4 years ago
링크
2^25 번 탐색하며, 7개의 좌표를 고른다.
7개의 숫자를 고른 뒤에 각 좌표들이 서로 연결되어있는지 탐색한다.
탐색할 때는 BFS를 이용해 탐색하며, 7개의 지점이 모두 연결되어있는지 탐색한다.
2^25 * 7 = 33,554,432 * 7 = 234,881,024
이므로 backtracking을 적용하지 않으면 제한 시간 내에 불가능하다.
5^2 크기의 2차원 boolean 배열을 선언해 사용한다.
'임도연파'가 4명 이상인 경우는 조합이 불가능하다. 따라서 탐색을 진행하며 임도연파가 4명 이상인 경우에는 더 이상 탐색하지 않는다.
연결관계의 확인은 BFS를 이용해 진행한다.
7개의 좌표 중 한점을 시작점으로 잡고 BFS로 탐색한다.
모든 점을 방문한 경우 전부 연결되어있고, 방문하지 못한경우 연결되어있지 않다.
맨 끝점일 때 link를 체크하지 않고 바로 return 해서 틀렸었다.
1941. 소문난 칠공주
링크
설계
시간 복잡도
2^25 번 탐색하며, 7개의 좌표를 고른다.
7개의 숫자를 고른 뒤에 각 좌표들이 서로 연결되어있는지 탐색한다.
탐색할 때는 BFS를 이용해 탐색하며, 7개의 지점이 모두 연결되어있는지 탐색한다.
이므로 backtracking을 적용하지 않으면 제한 시간 내에 불가능하다.
공간 복잡도
5^2 크기의 2차원 boolean 배열을 선언해 사용한다.
backtracking
'임도연파'가 4명 이상인 경우는 조합이 불가능하다. 따라서 탐색을 진행하며 임도연파가 4명 이상인 경우에는 더 이상 탐색하지 않는다.
연결관계 확인
연결관계의 확인은 BFS를 이용해 진행한다.
7개의 좌표 중 한점을 시작점으로 잡고 BFS로 탐색한다.
모든 점을 방문한 경우 전부 연결되어있고, 방문하지 못한경우 연결되어있지 않다.
정리
고생한 점
맨 끝점일 때 link를 체크하지 않고 바로 return 해서 틀렸었다.