본문 바로가기

전체 글

백준 10026 적록색약 DFS(깊이 우선 탐색)을 활용하는 문제이다. 2D 맵을 쓰는것을 보고 이건 BFS인가 DFS인가 했는데 경로를 찾는게 아니라 일단 DFS로 생각했고, 그쪽 접근이 나쁘지 않았다. 이전에 MST 문제를 풀 때, 2D로 된 섬들이 있는 맵에서 MST를 찾는 문제가 있었다. 해당 문제에서는, 지도에 섬이 몇개 있는지 알아야 했고, 맵에 있는 각 섬 픽셀이 어느 섬에 속해있는지 찾아야 했다. 그 과정에서 DFS를 사용해 섬 그루핑을 했는데, 그것과 거의 동일하게 이번 문제 풀이가 진행된다. 문제 풀이의 흐름은 다음과 같다. 어떤 특정한 픽셀에서 시작한다. 그 픽셀에서 상하좌우 픽셀을 탐색한다. 넘어온 픽셀이 탐색되지 않은 픽셀이고, 넘어오기 전 픽셀 색과 같으면 탐색 배열에 현재 그룹의 인덱스를 적어둔다. 2.. 더보기
백준 1963 소수 경로 BFS 문제중에 좀 특이하게 맵 탐색이 아닌 다른 공간을 탐색하는 문제이다. 어떤 4자리 소수에서 각 자리수를 바꿔가며 다른 소수로 이동하면서 탐색을 하게 된다. 따라서 일단 소수를 찾아놓고, 각 자리수를 바꾼 숫자가 소수인지 확인해야 한다. 소수를 찾아놓을 땐, 에라토스테네스의 체를 이용해 정해진 범위(10000)까지의 소수를 찾는다. memset(filter, 1, sizeof(filter)); filter[0] = 0; filter[1] = 0; for (int i = 2; i < 10000; i++) { if (filter[i]) { for (int j = 2*i; j < 10000; j+=i) filter[j] = 0; } } 그리고, 탐색을 하는 과정에서 각 자리수를 바꿔야 하므로 조금 더 편.. 더보기
백준 2206 벽 부수고 이동하기 BFS를 사용해 맵을 탐색하는 문제이다. 단순히 출발지에서 도착지까지 탐색하는것에 더해, 우리의 플레이어는 원래는 가지 못하는 벽을 한번 부수고 통과할 수 있다.(이하 슈퍼파워) 이 부분에 있어서 살짝 꼬여진 문제라고 볼 수 있다. 일반 BFS 탐색 코드와 달라지는 점은, visited 배열이 달라진다는것과 큐에 넣을때 두 가지 조건(벽을 부수는 경우, 아닌 경우)을 따져야 한다는 점이다. visited[0 or 1][N][M] 배열은, N*M 크기 맵에서 해당 픽셀을 벽을 부수고 나서 도달하였는가(1), 벽을 부수지 않고 도달하였는가(0)을 의미한다. 해당 visited 배열을 보고, 큐에 넣을 때의 조건을 따진다. 다음 방문 픽셀이 벽이고, 벽을 부술 수 있으며, 벽을 부수고 방문하지 않은 경우 ->.. 더보기
[나만 몰랐던 알고리즘] 2D 맵 BFS Breadth-First-Search. 넓이 우선 탐색이다. 2D 맵 나오고 뭐 최단거리 찾아라 이런 문제에 접근 방식을 잘 모르겠어서 찾아보던 와중, 그런 문제는 BFS로 탐색하면 좋다고 해서 알아보았다. 문제 뿐만이 아니라 2D 맵 탐색에 막연한 두려움을 가지고 있어 한번 정리해 보았다. 맵은 2차원 int 배열로 만든다. 탐색을 할 때, 방문한지 여부를 visited 배열에 저장한다. 이 visited 배열은 문제마다 다를 수 있지만, 대개 map 크기와 같다. BFS 의 탐색 특징은 FIFO(First In First Out)이다. queue를 사용해 방문과정을 탐색한다. 현재 상황이나 위치를 구조체로 정의해두면 편하다. 탐색을 할 때 사용할 4방위(상하좌우)나 8방위(상하좌우, 좌상 우상 좌하 .. 더보기
백준 1626 두 번째로 작은 스패닝 트리 LCA - 최소 공통 조상을 사용하는 문제이다. 두 번째로 작은 스패닝 트리를 구할 때, MST에 포함되어있지 않은 에지를 골라서 그 에지가 잇는 두 노드의 경로 중 최대값 에지를 빼는 과정이 필요하다. 두 노드의 최단 경로를 찾을 때 LCA 알고리즘을 사용한다. 여기에, "두 번째로 작은" 이라는 조건이 붙으므로, 추가된 에지 비용과 경로 중 최대값 에지의 비용이 같으면 안된다. 그 다음으로 큰 에지를 골라야 한다. 여기까지 생각해보면, LCA에서 사용한 parents[K][V] 배열은 그대로 있어야 하고, path[K][V]를 만들어서 V에서 2^K 조상까지의 경로를 벡터형식으로 저장을 하면 좋을 것 같다. 나중에 두 노드에서 LCA까지 경로를 전부 아니까 거기서 MST 비용보다 큰 노드를 찾기만 하.. 더보기
백준 15481 그래프와 MST 역시 LCA를 활용하는 문제이다. 저번 정점들의 거리 문제에서 MST의 개념을 살짝 붙이기만 하면 방법을 찾을 수 있다. 에지를 입력받을 때, 인접 행렬을 직접 만드는 것이 아니라, 에지만 저장하는 벡터/배열을 선언하고 나중에 그 에지들을 순회하며 MST를 찾을 수 있게 한다. std::vector adj[N]; std::priority_queue pq; std::vector vEdgeList; 일단 에지를 입력받고 난 다음, 그 에지들을 사용해 MST를 계산한다. MST를 계산하면서 adj(인접행렬)을 채워 이 트리를 사용해 LCA를 구하게 된다. for (int i = 0; i > s >> e >> c; s--; e--;.. 더보기
백준 1761 정점들의 거리 LCA를 활용하는 문제이다. LCA 분류 문제만 풀다보니 거의 같은 코드에 조금만 바꾸는 느낌이 계속 든다. 근데 LCA 알고리즘은 진짜 신기한것 같다. 관련 포스팅을 몇개 연속해서 써도 얘가 돌아가는 매커니즘이 계속 신기하다. 2진수 사고방식을 쉽게 머리속에서 굴릴 수 있는 사람이 처음 만든 것 같은데, 어쩜 저런 생각을 했는지... 각설하고. 이번 문제는 이전에 있었던 도로 네트워크 와 거의 유사하다. 중간중간 코드 몇줄만 바꿀정도. LCA에 대한 개념부터 보고싶다면 LCA 설명 글도 있다. 도로 네트워크에서는 parents[] 배열 이외에 pathMax[K][V], pathMin[K][V] 배열이 존재해 각각 2^K 번째 노드까지 경로 중 cost가 최소인 것과 최대인 것을 저장했었다. 이 문제에서.. 더보기
백준 3176 도로 네트워크 LCA를 활용하는 문제이다. 두 도시를 연결하는 경로는 LCA를 통해 구할 수 있다. 두 노드 u, v에서 LCA까지 이르는 경로를 합치면 두 도시를 있는 최소 경로가 된다. LCA 2 에서는 parents[] 배열에 2^K 번째 부모 노드들을 저장했었는데, 이것을 응용해 2^K 번째 부모 노드까지의 경로에서 에지의 최소값을 저장하는 배열과 최대값을 저장하는 배열을 만들기만 하면 문제를 해결할 수 있다. LCA 2에서 달라질것은, pathMax[] 배열과 pathMin[] 배열을 새로 만든것과, Parents[] 배열을 초기화하거나 갱신할때 새로 만든 두 배열도 값을 넣어준다는 것, 두 노드의 높이를 맞춰주거나 맞춘 후 위로 탐색할때 u와 v가 움직이는것에 맞춰 탐색되는 경로 상 최대/최소값을 찾아준다는.. 더보기

티스토리툴바