본문 바로가기
반응형

dfs5

[C/C++] 백준 #2573 빙산(깊이 우선 탐색) 이번 문제는 보다 좋은 알고리즘을 택하기 보다는 구현을 위주로 하였습니다. 깊이 우선 탐색은 섬의 개수가 몇개인지 판단하기 위해서 사용을 하였습니다. 문제 링크입니다. https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제는 빙하가 같은 높이만큼 녹을 때, 한덩어리의 빙하가 두덩어리 이상이 되는 최소 녹는 높이를 구하는 것입니다. 구현 자체는 간단합니다. 빙하가 녹는 높이에 따라서 빙하가 두개가 될 때의 높이를 출력하게 하였습니다. 제가 구.. 2023. 7. 30.
[C/C++] 백준 #2146 다리 만들기(DFS, BFS) 이번 문제는 최단거리를 찾는 문제이긴 하지만, 이동하는데 드는 비용이 항상 같기 때문에 너비 우선 탐색을 사용하면 되는 문제입니다. 문제는 아래의 링크입니다. https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 이 문제를 풀 때에는 두 단계를 걸쳐서 풀었습니다. 일단 섬마다 고유한 아이디를 부여하기 위해서 깊이우선탐색(DFS)을 이용해서 고유 아이디를 붙였습니다. 다음으로는 모든 섬에 대해서 다리를 놓기 위한 최단 거리를 구하는 작업을 하였습니다. 이 .. 2023. 4. 10.
#1405 미친 로봇(Full Search, Back Tracking) 이번 문제는 경로를 다니면서, 지나온 길을 거치지 않을 확률을 계산하는 것입니다. 난이도 Gold V로 어렵지는 않은 문제이고요. 복잡한 알고리즘이 아니라, 단순한 백트랙킹을 구현하면 됩니다. 동서남북으로 움직일 수 있는 확률이 주어지고, 동서남북으로 확률적으로 N칸 움직였을 때, 지나온 경로를 다시 방문하지 않는 경로로 움직일 확률이 얼마일까를 계산하는 문제입니다. 예를 들어서 로봇이 NESW로 순차적으로 움직였다면, 원위치로 돌아왔으니, 지나온 경로를 지나게 됩니다. NNES 라던지, SWWS 와 같은 경로는 4칸을 움직이면서 지나온 경로를 지나지 않는 움직임이 됩니다. 문제를 풀기 위해서는 BFS, DFS 들 중 어떤 것을 사용하든 상관이 없습니다. 전 편한 DFS를 사용했습니다. 최대 움직임은 1.. 2020. 2. 23.
#1325 효율적인 해킹(DFS) 이번 문제는 Silver II 난이도의 문제입니다. 저는 처음에 너무 단순하게 생각해서 한번 틀렸네요. 신뢰관계의 종속성이라는 문제때문인데요. A 가 B를 신뢰하고, B가 C를 신뢰하면, A가 C를 신뢰한다는 사실입니다. 이에 대한 이해도가 틀리면, 해결방법도 당연히 틀리겠죠. 문제의 요지를 살펴보면, N개의 컴퓨터들이 있고, M개의 신뢰관계가 존재할 경우에, 신뢰를 받는 최상위 컴퓨터를 찾는 것입니다. 예를 들면 다음의 그림과 같이 5대의 컴퓨터가 있고, 4개의 신뢰관계가 주어졌다고 해보죠. 화살표 방향으로 신뢰관계가 주어집니다. E는 C를 신뢰하고, C는 A와 B를 신뢰합니다. 직관적으로 보면, 저 위의 그림의 경우에 A 또는 B를 해킹하면, 총 4대의 컴퓨터를 한번에 해킹할 수 있습니다. 전 이 문.. 2020. 1. 24.
#1303 전쟁 - 전투 (DFS) 이번 문제는 Silver I 문제로 기초적인 DFS 문제입니다. 핵심은 연결된 지역의 수를 알아내는 것으로, "섬의 개수" 등과 같은 문제와 동일합니다. MxN 지역(보통은 NxM인데, 여기서는 MxN입니다.)에 W로 마킹된 곳과 B로 마킹된 곳이 있습니다. 대각선으로는 이어질 수 없고, 상하좌우로만 이어집니다. 서로 이어진 곳을 하나의 집단이라고 한다면, 그 집단의 구성수의 제곱을 합한 것이 전투력이 됩니다. 이 전투력을 각각의 집단 'W'와 'B'를 표시하면 됩니다. DFS로 해결해도 되고, BFS로 해결해도 되는 문제입니다. 저는 개인적으로 DFS를 선호합니다. 결국 큐 자료구조를 선호하느냐 아니면 스택자료 구조를 선호하느냐의 차이겠죠. 또한 경계선 검사를 할 때, 미리 더 넓은 지역을 잡아놓고 새.. 2020. 1. 19.
728x90

티스토리툴바