프로그래밍/알고리즘
BOJ 14496 · 그대, 그머가 되어
알고리즘 분류 : BFS 야민정음을 통해 A 문자를 B 문자로 치환할 때, 최소 치환 횟수를 구하는 문제다. 인접 리스트 기반의 BFS 문제로 보면 된다. 입력으로 주어지는 치환 문자쌍을 인접 리스트로 만든다.문자 A부터 BFS 탐색을 시작하여 문자 B까지 도달하는 최소 횟수를 구하면 된다. C++ 소스코드 #include #include #include #include using namespace std; int a, b, n, m; vector v[1001]; int dist[1001]; void bfs() { queue q; q.push(a); dist[a] = 0; while (!q.empty()) { int x = q.front(); q.pop(); if (x == b) { printf("%d\..
BOJ 13903 · 출근
알고리즘 분류 : BFS 출근하기 위해 필요한 최소 걸음을 구하는 문제다. BFS를 통해 최소 횟수를 구하면 된다. 첫 번째 줄부터 시작해서 마지막 줄에 도착하면 출근에 성공한 것이다. 마지막 줄에 도달하지 못하면 출근할 수 없다. 이동 방법이 정해져 있지 않으므로, 이 부분만 잘 구현하면 일반적인 BFS 문제와 비슷하다. R*C 사이즈의 맵을 기준으로, 0번째 줄에서 출발하여 R-1번째 줄에 도착하면 출근이 가능한 것이다.0번째 줄에 있는 세로 블록(1)을 큐에 모두 집어넣는다.입력으로 주어지는 이동 규칙에 따라 이동을 한다. 가로 블록(0)으로는 이동할 수 없다.R-1번째 줄에 도착하면 이동 횟수를 출력하고, 만약 도착할 수 없다면 -1을 출력한다. C++ 소스코드 #include #include u..
BOJ 13700 · 완전 범죄
알고리즘 분류 : BFS S부터 출발하여 D에 도착하는 최소 이동을 구하는 문제다. BFS를 이용하여 구하면 된다. S부터 시작하여 BFS 탐색을 진행한다.현재 위치가 X라 할 때, 다음 위치는 X+F (→이동) 또는 X-B (←이동)이 된다.K개의 경찰서를 제외한 곳으로 이동하면서 최소 이동 횟수를 구하면 된다. C++ 소스코드 #include #include #include using namespace std; int n, s, d, f, b, k; int dist[100001]; void bfs() { queue q; q.push(s); dist[s] = 0; while (!q.empty()) { int x = q.front(); q.pop(); if (x == d) { printf("%d\n", ..
BOJ 13746 · Islands
알고리즘 분류 : DFS 주어진 맵에 존재하는 섬의 최소 개수를 구하는 문제다. 전형적인 플러드 필 문제이다. 맵에서 땅('L')을 시작점으로 하여 DFS 탐색을 한다.구름('C')은 땅 또는 물이 될 수 있으므로, 이동 가능하다.물('W')로는 이동할 수 없다.모든 땅의 탐색이 끝날 때까지 진행한다. C++ 소스코드 #include int r, c, ans; char a[51][51]; bool check[50][50]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; void dfs(int x, int y) { check[x][y] = true; for (int i=0; i
BOJ 13565 · 침투
알고리즘 분류 : BFS 바깥쪽부터 안쪽까지 전류가 침투할 수 있는지 확인하는 것을 구현해야 한다. 바깥쪽은 첫 번째 행이며, 안쪽은 마지막 행이다. 첫 번째 행부터 BFS 탐색을 시작해서 마지막 행에 도달하는지 확인해보면 된다. 0 번째 행에 있는 모든 흰색 격자(0)의 좌표를 큐에 집어넣는다.BFS 탐색을 시작하여 N 번째 행까지 도달하는지 확인한다. 차단 물질(1)로는 이동할 수 없다.N-1 번째 행에 도달하면 전류가 침투 가능한 것이므로 "YES"를 출력하고 탐색을 종료한다.BFS 탐색이 끝날 때까지 N-1 번째 행에 도달하지 못하면, 침투 불가능한 것이므로 "NO"를 출력한다. C++ 소스코드 #include #include using namespace std; struct grid { int ..
BOJ 12273 · Dragon Maze (Large)
알고리즘 분류 : BFS 드래곤이 파워를 모으면서 탈출하는 것을 구현하는 문제다. BFS를 통해 맵을 탐색하면서 구하면 된다. 비슷한 문제로 BOJ 12272번 'Dragon Maze (Small)'이 있다. Small 문제는 Large 문제보다 범위만 적은 것이므로, 같은 코드로 해결 가능하다. 입구에서 출구까지 최단 거리로 이동해야 한다. 단, 정답은 이동하면서 얻은 파워 합의 최댓값이다.따라서 일반적인 큐(Queue)를 쓰는 것보다, 우선순위 큐(Priority Queue)를 이용하는 것이 좋다.이동 거리가 짧을수록, 파워 합이 클수록 우선순위가 높도록 처리한다. 우선순위 큐에 (이동거리, 파워, X 좌표, Y 좌표) 순으로 넣는다.맵을 탐색하면서 위험지역(-1)을 제외한 곳으로 이동한다. 이동한 ..
BOJ 11370 · Spawn of Ungoliant
알고리즘 분류 : DFS 거미가 영역을 확장하는 것을 구현하면 된다. 전형적인 플러드 필 문제이다. 거미의 위치('S')부터 시작해서 DFS로 뻗어나간다.나무('T')에만 뻗어나갈 수 있으며, 거쳐간 나무는 'S'로 바꾼다. C++ 소스코드 #include int h, w; char a[101][101]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; int dfs(int x, int y) { for (int i=0; i
BOJ 11123 · 양 한마리... 양 두마리...
알고리즘 분류 : DFS 양 무리를 세는 문제이다. 전형적인 플러드 필 알고리즘이다. H*W 사이즈의 맵을 DFS로 탐색한다.양(#)부터 시작해서, 연결된 양을 찾는다.맵을 모두 탐색할 때까지 진행하여, 양 무리를 카운트한다. C++ 소스코드 #include #include int h, w; char a[101][101]; bool check[100][100]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; int dfs(int x, int y) { check[x][y] = true; for (int i=0; i