1. 힙 없이 완전 탐색 1. 출발지에서 다른 노드들까지의 거리를 저장한다. (각 노드까지의 최단거리를 갱신해가는 과정) 직접 연결되지 않은 노드들은 거리를 무한대로 놓는다. 출발지를 들렀다고 표시한다. 2. 들르지 않은 노드 가운데 가장 가까운 노드를 선택한다. 3. 선택한 노드를 거쳐서 직접 연결된 다른 노드까지 도달하는 거리가 이미 저장된 거리보다 짧다면 최단 거리를 갱신한다. 4. 2~3을 모든 노드를 방문할때가지 반복한다. 모든 노드를 들르면서 위의 과정을 진행하기 때문에 O(N) 의 연산이 필요하다. 거기에 2번을 완탐으로 탐색하게 되면 매번 O(N)이 걸리므로 총 O(N^2) 이 필요한 알고리즘이다. 2. 최소힙 사용 2. '기장 가까운 노드 찾기'를 더 빠르게 수행하기 위해 최소힙을 사용해..
(python3) 아이디어 까다로운 상어 시리즈의 청소년 버전입니다. 이 문제는 시뮬레이션의 조건이 많기 떄문에 코딩 과정에서 스텝이 꼬이지 않도록 기능을 잘 분리해서 접근해주는게 좋습니다. 저는 위치가 2차원 행렬로 표현되는 경우 x,y 보다 r,c 를 사용하는게 명료해서 더 선호합니다. 방향 역시 1~8 의 숫자로 문제에서 주어졌지만 배열로 접근할때의 편의성을 위해 0~7 로 변환하여 사용했습니다. 이런 디테일한 변수 설정들이 헷갈리지 않도록 메모하거나 체계를 잡아두는게 좋은 것 같습니다. 상어가 이동할 수 있는 모든 경우의 수를 탐색해야하고, 이전의 선택 뒤에 다음 선택지가 가지치듯 갈라지는게 반복되기 때문에 백트레킹을 사용하는게 좋습니다. 재귀를 활용해서 단순하게 구현이 가능합니다. 백트래킹은 트..
(python3) 구현 아이디어 각 기능을 구현한 함수명을 함께 작성했습니다. 1. 벽 3개를 세울 수 있는 모든 방법을 찾아야 합니다. next() 는 바로 다음 빈칸을 찾습니다. next_wall() 에서는 다음 벽 3개 조합을 찾습니다. 3번 벽을 한칸 다음으로 옮겨보고, 옮길 공간이 없으면 그 2번 벽을 한칸 다음으로, 3번 벽은 2번 벽 바로 다음으로 배치합니다. 이때 3번 벽이 또 갈 곳이 없다면 1번 벽을 한칸 다음으로 옮기고 그 다음에 2번, 그 다음에 3번 벽을 배치합니다. 이때 3번 벽을 배치할 공간이 없으면 모든 벽의 조합을 다 확인해본 꼴이 됩니다. 2. 벽을 세우고, 맨 처음 배치되어 있는 모든 바이러스에 대해 dfs 를 수행하여 바이러스가 다 퍼진 뒤의 상태를 확인합니다. (in..
