BFS

출처 Programmers 등산코스 정하기(2022 KAKAO TECH INTERNSHIP) 접근 문제 분석 산의 봉우리까지 이동하는 과정을 시뮬레이션 하는 문제입니다. Intensity는 이동 과정에서 가장 긴시간을 뜻합니다. 문제에서는 정상에 도착한 후, 다시 출입구로 돌아와야 한다고 했지만 올라갔던 길을 그대로 내려올 수 있기 때문에, 정상까지만 경로를 추적하면 됩니다. 따라서 각 출발지(Gate)에서 도착지(Summit)까지의 Intensity가 최소가 되도록 완전탐색을 수행해야 합니다. 조건 분석 문제에서 주어진 정점(Vertex)은 n = 50,000 이고 간선(Edge)은 paths = 200,000입니다. 탐색의 시작점이 최대 n이기 때문에, 각 간선을 1번씩만 방문하도록 최적화하면 시간복잡도 내 문제를 해결할 수 있습니다. O(N) = n + paths = 250,000 ...

출처 SWEA 1249 보급로 접근 시간복잡도 계산 N <= 100, 지도의 최대 크기가 10000이므로, 방문 체크만 잘 해주면 완전탐색을 하는데 큰 문제가 없는 조건입니다. BFS BFS(너비우선 탐색)를 통해 최단경로를 구할 수 있습니다. 이 때, 미로찾기 알고리즘처럼 목적지에 도착하면 끝나는 것이 아니라, 가중치가 가장 낮은 경로로 이동해야 합니다. 따라서, 이미 목적지에 도착했더라도 더 빠른 경로가 있기 때문에 BFS를 종료하면 안됩니다. 위 그림에서 우 -> 하 순으로 탐색을 진행할 경우, 전체 비용이 6인 경로가 먼저 탐색되지만 비용이 가장 작은 경로는 아닙니다. 이를 위해, 각 지점마다 도달할 수 있는 최소 가중치를 저장해두고, 해당 가중치보다 작은 값만 재방문이 가능하도록 하여 방문 횟수를 줄일 수 있습니다. ...

출처 메두사와 전사들 접근 복잡한 문제인만큼 구현하면서 순차적으로 처리해야 할 과정이 많은데, 이에 필요한 알고리즘을 정리해보면 다음과 같습니다. 메두사의 이동경로 구현 BFS + 경로 역추적 시선 생성 배열 탐색 구현 병사 이동 및 공격 배열 탐색 구현 알고리즘 자체는 어렵지 않으나, 배열 탐색을 구현하는 과정이 복잡합니다. 메두사 이동경로 구현(BFS) 메두사가 이동하는 과정에 장애물이 있기 때문에, BFS를 통해 미로를 탐색하는 최단경로를 구해야 합니다. 또한, 이동경로를 다시 돌면서 병사들과의 상호작용을 확인하기 위해 이러한 경로를 별도 배열에 저장해야 합니다. ...

출처 백준 1005 ACM Craft 접근 완전탐색(BFS) 특정 건물이 나올때까지 각 건물들을 탐색하는 과정을 BFS로 구현할 수 있습니다. 건물 사이의 관계(간선)의 개수가 100,000이므로, 각 간선을 한번씩만 방문한다면 시간복잡도 내 풀이가 가능합니다. 위상 정렬 각 건물은 해당 건물이 지어지기 전에 특정 건물을 지어야 하는 선행조건이 있습니다. 이를 구현하기 위해 위상정렬을 활용할 수 있습니다. 위상정렬은 다음과 같이 해당 건물을 짓기 전에 선행되어야 하는 건물이 모두 지어졌는지(선행 건물의 개수가 0인지) 확인하는 과정을 통해 구현할 수 있습니다. ...

출처 https://www.acmicpc.net/problem/2573 접근 각 칸이 10이하이고 전체 칸은 10,000이므로 빙산을 모두 녹이려면 10 _ 10,000 _ 10,000이지만, 네 변이 노출되면 금방 사라지므로 완전탐색이 가능하다고 판단했습니다. 매 회마다 빙산을 녹이고, 빙산을 bfs(dfs)로 탐색해서 두 덩어리가 있는지 확인한다. 모든 빙산이 다 녹았지만 2개로 분리되지 않는 경우를 주의한다.1 풀이 package solving; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; /* * [조건] * 시간제한 : 1초, 메모리 제한 : 256MV * 이차원 배열의 크기가 300^2 이하이며 전체 칸의 개수는 10,000개 이하, 각 칸의 크기는 10 이하 * [풀이] * 각 칸이 10이하이고 전체 칸은 10,000이므로 빙산을 모두 녹이려면 10 * 10,000 * 10,000이지만, 네 변이 노출되면 금방 사라지므로 완전탐색 * 매 회마다 빙산을 녹이고, 빙산을 bfs로 탐색해서 두 덩어리가 있는지 확인한다. */ public class bj_2573_빙산 { static int N, M, count; static int[] dr = {0, 0, 1, -1}; static int[] dc = {1, -1, 0, 0}; static int[][] pole; public static void main(String[] args) throws IOException { // 초기화 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); pole = new int[N][M]; for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < M; j++) pole[i][j] = Integer.parseInt(st.nextToken()); } count = 0; // 빙산을 녹이면서 두 개로 분리되는지 확인 while (!isFinished()) { melt(); count++; } System.out.println(count); } // 빙산 녹이기(녹은 값을 별도의 리스트에 저장 후 마지막에 반영) private static void melt() { List<int[]> melted = new ArrayList<>(); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (pole[i][j] == 0) continue; int now = pole[i][j]; for (int k = 0; k < 4; k++) { int nr = i + dr[k]; int nc = j + dc[k]; if (nr < 0 || nr >= N || nc < 0 || nc >= M || pole[nr][nc] != 0) continue; now --; } if (now < 0) now = 0; melted.add(new int[] {i, j, now}); } } for (int[] now : melted) pole[now[0]][now[1]] = now[2]; } // 2개로 분리되었는지 확인(BFS) private static boolean isFinished() { // 두 덩이로 분리되지 않고 모든 빙산이 녹았을때 예외처리(중요) int sum = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { sum += pole[i][j]; } } if (sum == 0) { count = 0; return true; } // BFS 초기화 Queue<int[]> q = new ArrayDeque<>(); boolean[][] isVisited = new boolean[N][M]; boolean isOneBlock = false; // 한 얼음을 만날때까지 확인 for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (!isVisited[i][j] && pole[i][j] != 0) { // 이미 얼음을 만났음에도 다시 만난 경우 true(빙산이 2개로 나눠짐) if (isOneBlock) return true; isOneBlock = true; // BFS를 돌면서 방문처리 q.offer(new int[] {i, j}); isVisited[i][j] = true; while (!q.isEmpty()) { int[] now = q.poll(); for (int k = 0; k < 4; k++) { int nr = now[0] + dr[k]; int nc = now[1] + dc[k]; if (nr < 0 || nr >= N || nc < 0 || nc >= M || pole[nr][nc] == 0 || isVisited[nr][nc]) continue; isVisited[nr][nc] = true; q.offer(new int[] {nr, nc}); } } } } } return false; } } 결과 ...