본문 바로가기

알고리즘/Baekjoon

 (196)
최단경로. [9370] [1. 문제 설명] 임의의 출발지에서 임의의 목적지들에 최단 경로로 갈 때, 특정 경로를 거치는 경로 역시 각 목적지들에 대해 최단 경로가 될 수 있는가? [2. 풀이 접근] A. 오답이었던 접근 방법 1 다익스트라 탐색 중, 특정 경로를 통과한 정보를 추가로 저장함 (from -> to 가 문제에 제시된 각 노드라면 true, 그렇지 않다면 false) 다익스트라 탐색 중, 목적지 노드에 도착한 경우, from node 내 정보를 토대로, 특정 경로를 통과했다면, 해당 목적지는 특정 경로를 통과했다고 저장. (경로 코스트의 합이 최소랑 같다면 => 최단 경로가 여러개 있는 것으로, true 일때 만 저장(default: false), 경로 코스트의 합이 최소라면 => true, false 상관 없이 저..
최단 경로. [13549] [1. 문제 설명] 수평선의 임의 시작점에서 특정 위치까지 가장 빨리 이동할 때 걸리는 시간 현재 위치 x에서 1초 후에 x-1, x+1 로 이동하거나 0초 후에 순간이동 할 경우 2x 위치로 이동할 수 있음. [2. 풀이 접근] 다익스트라로 접근 할 필요는 없음 이동하는데 걸리는 시간은 0 아니면 1이고, 순간이동하는 경우는 같은 노드로 봐도 되므로, (x 나 2x 나 방문 순서가 같다.) 모든 edge 는 1 의 가중치를 갖는다고 볼 수 있음 따라서, bfs 로 최단 경로를 구할 수 있다. 1차 풀이에서 틀렸 던 점은 왼쪽으로 이동하는 경우 x 가 음수가 될 수 있는데, 이에 대한 예외처리 (out of bound) 를 하지 않은 것이다. [3. 코드]
최단 경로. [1504] [1. 문제 설명] 임의로 주어진 두 정점을 반드시 통과하면서 1번 정점에서 N번 정점으로 최단거리를 구한다. (이 과정에서 한번 이동했던 정점은 물론 간선도 다시 이동 할 수 있다.) [2. 풀이 접근] A. 오답이었던 접근 방식 현재 반드시 지나야 하는 정점의 개수를 기록하여 int costs[2][N]; 을 업데이트 함 => 비슷한 문제가 있었음. (https://testkernelv2.tistory.com/337) 반드시 지나야 하는 정점의 개수를 셀 때, 같은 정점을 두번지나는 경우를 방지하기 위한 처리 => 현재 인접 정점을 테스트 할 때, heap 에서 pop 한 노드에 저장된 slice 를 순회하여 같은 정점인지 아닌지를 체크 후, 업데이트 한번에 다익스트라 실행으로 답을 구할 수 있을 것..
최단 경로. [1753] [1. 문제 설명] 방향그래프에서 edge 의 weight 가 주어질 때 시작점에서 그래프 내 모든 정점에 최단 거리로 방문할 때, 모든 정점의 최단 거리 값을 출력한다. [2. 풀이 접근] 다익스트라는 우선순위 큐를 사용하여 구현 할 경우 그 시간 복잡도는 아래와 같다 O(V + ElogV) 이며, 여기서 E 는 Edge 의 개수, V 는 Vertex 개수 이다. heapify 에 대하여 처음 풀이에서 heapify 를 하여 우선순위를 재조정하는 코드가 있었다. => 힙에 이미 푸쉬되었지만, 다른 경로를 거쳐 오는 경우가 더 빠른 경우 가 발생할 수 있으므로 실행시간이 다소 늦음 => heap 에 푸쉬된 특정 정점을 찾기 위해 O(n) 에 시간이 걸리기 때문 => heap 은 오름/내림 차순 등으로 정..
그래프와 순회. [1707] [1. 문제 설명] 주어진 그래프가 이분 그래프인지 아닌지 판별한다. [2. 풀이 접근] 이분 그래프란? 그래프의 모든 정점이 두 그룹으로 나누어지고, 서로 다른 그룹의 정점들은 연결되지만(인접하지만), 같은 그룹의 정점들은 서로 연결되지 않는(인접하지 않지만) 그래프 인접한 정점은 서로 다른 그룹에 속해야 하므로 bfs 로 모든 정점을 순회하는데 바로 인접한 정점은 현재 정점과 무조건 반대 그룹에 속하도록 한다. (다른 그룹 번호를 할당) 그런데, 인접 정점이 이미 방문되었고, 그 그룹이 자신과 같은 그룹 번호라면 이 경우, 이분 그래프가 될 수 없다. [3. 코드]
그래프와 순회. [2206] [1. 문제 설명] NxM 맵에서 [1, 1] 에서 [N,M] 으로 최단 경로를 출력하는데, 벽을 부수고 이동하는 것이 최소라면 벽을 최대 하나까지만 부수고 이동할 수 있다. [2. 풀이 접근] A. 잘못된 접근 일반 bfs 접근 중, 이동하려는 벽이 막혀있으면, 일단 부시고, 백업 큐에 저장 => 이미 부수고 온 경우라면, 이 위치에서는 더 이상 부수지 않고 스킵함. 부수지 않고 이동해온 경우로 마지막 좌표에 도달 할 수 없는 경우, 백업 큐에 저장한 것을 이용하여 bfs 를 수행 이 풀이가 틀린 이유는? 벽을 부수지 않고 이동한 경우 도달 할 수는 있으나, 벽을 부수고 이동한 것이 최소 일 수 있기 때문 B. 올바른 접근 visits 테이블에 차원을 하나 추가 => 벽을 부수고 이동한 경우와 그렇지 ..
그래프와 순회. [16928] [1. 문제 설명] 1번 칸에서 시작해서 주사위를 굴려 나온 수 만큼 이동 하여, 100번 칸에 도달 할 때, 주사위를 굴려야 하는 최소 횟수 (특정 칸에서는 사다리를 타고 앞쪽 칸 으로 이동하거나, 뱀을 타고 뒤쪽 칸으로 이동 할 수 있다.) [2. 풀이 접근] 문제 상에서는 10x10 크기의 게임판이라는 표현이 있지만, 10x10 의 2차원 배열로 게임판을 모델링 할 필요는 없다. 사다리와 뱀에 대한 정보를 따로 취급 할 필요는 없다. 어차피 특정 칸으로 점프 하는 개념이기 때문이다. bfs 로 풀어야 하는 이유(?) 일단 어떤 칸에서 +1, +2, ... +6 만큼 떨어진 위치로 이동하는데 필요한 비용은 모두 같다.(edge 에 별다른 weight 가 없다.) 특정 노드까지 최대한 빨리 도달해야 한..
그래프와 순회. [7576] [1. 문제 설명] 창고 내 한 격자에 토마토 한개를 보관 할 수 있다. 익은 토마토 하나는 인접한 곳에 익지 않은 토마토를 익게 할 수 있다. 창고 내 모든 토마토가 익는데 걸리는 최소 일수를 구하도록 하고, 모든 토마토가 익을 수 없는 경우 -1 을 출력 한다. [2. 풀이 접근] 잘못 된 접근 아직 방문하지 않은 좌표 중, 익은 토마토 위치에서 bfs 를 시작, 이 과정을 마지막 좌표까지 반복 => 처음에 익은 상태에 모든 토마토에서 이 과정이 동시에 시작되어야 함. => 위 방법은 잘못된 계산을 유도할 수 있음. 아래와 같이 A 와 B 가 모두 익은 상태인 경우, x3 가 익는 시점은 3 이 아니라 1 이다. => A - x1 - x2 - x3 - B 올바른 접근 최초 익은 토마토의 위치를 모두 ..
그래프와 순회. [7562] [1. 문제 설명] 현재 나이트 위치에서 다음 나이트 위치까지 이동 할 때, 필요한 최소 이동 횟수 [2. 풀이 접근] BFS 탐색은 DFS 와 달리 특별한 성질이 있다. 그 성질은 각 정점을 최단경로 방문한다는 것이다. (단, 이 경우 Edge 의 weight 라는 개념이 없거나, 모든 weight 가 같아야 한다.) 아래와 같은 그래프를 정점1에서 시작해서 DFS 로 탐색 할 때 (인접한 정점을 오름차순으로 방문한다 가정) 정점6에 방문하기 위해서는 4개의 edge 를 거쳐야만 한다. 하지만, BFS로 탐색 시, 총 2개의 edge 만을 거치면 된다. 따라서, bfs 로 나이트를 특정 위치에 도달 할 때 가지 각 방향으로 이동시키면 된다. [3. 코드]
그래프와 순회. [2667], [1012] [1. 문제 설명] NxN 크기의 배열에서 아래,위로 인접한 집들을 하나의 단지로 묶을 수 있을 때, 전체 단지의 개수와 각 단지에 속한 집들의 개수를 오름차순으로 출력 (대각선으로 인접한 것은 취급하지 않는다.) [2. 풀이 접근] 인접한 집으로 이동 할 수 있다는 점에서 그래프 개념으로 접근할 수 있다. 어떤 위치에서 이동할 수 있는 방향은 상,하,좌,우 4가지가 되므로, 각 경우에 대해서 dfs 를 수행 해 볼수 있다. 그러나, 좌표를 움직여야 하므로, 좌표가 NxN 배열을 넘어 선 경우, 이미 방문한 좌표, 좌표에 해당하는 값이 0인 경우는 무시해야 한다. 또한 작성 한 dfs 함수는 최종적으로 하나의 단지의 포함 된 집의 개수를 반환하는데, 기저 사례를 통과한 경우 최소 하나의 집이 있음이 보장..

티스토리툴바