반응형 BFS28 [백준] 2146번 - 다리 만들기 (Java) https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net N x N인 맵에서 여러 개의 섬이 있다. 각 섬을 연결하는 다리를 한 개만 건설한다고 할 때 가장 짧은 거리를 구하라. BFS탐색으로 각 섬은 탐색할 수 있다. 그런데 각 섬과 다른 섬과 가장 최소거리는 어떻게 구하지? 시간 제한 : 2초 메모리 제한 : 192MB 지도크기 : N 2022. 10. 2. 플러드 필(Flood Fill) 알고리즘 플러드 필은 다차원 배열에서 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 그림판에서 색 채우기 명령으로 동일한 색을 전부 바꿔버리는 것과 동일하다. 플러드 필 문제는 BFS/DFS 알고리즘으로 풀 수 있다. [BFS의 풀이과정] 1. 시작하는 칸을 큐에 넣고 방문 표시를 한다. 2. 큐에서 원소를 꺼내어 그 칸에 상/하/좌/우로 인접한 4개의 칸에 대해 탐색을 한다. 3. 해당 칸을 이전에 방문했다면 무시하고, 처음 방문했다면 방문 표시를 하고 해당 칸을 큐에 넣는다. 4. 큐의 모든 원소가 빌 때까지 2를 반복한다. 5. 모든 칸이 큐에 1번씩만 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다. ※ 참고 : https://blog.encrypted.gg/941 2022. 10. 1. [백준] 2206번 - 벽 부수고 이동하기 (Java)(△) https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1. 최단거리 구하기 문제이므로 BFS 탐색을 사용하면 된다. 2. 벽을 한개까지 부술 수 있다. 탐색 시에 벽을 만나도 한번 더 나갈 수 있다는 뜻. 2-1. 최대 한개까지 1 -> 0으로 바꿀 수 있다. 2-2. 벽 공사 여부를 변수로 넣고 dist 배열을 dist[N][M][2]개로 만들어서 관리 2-3. 벽을 한번도 안 뚫은 경우는 dist[][][0]으로 거리 저.. 2022. 9. 20. [백준] 1753번 - 최단경로 (Java) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. 다익스트라 알고리즘을 사용 2. 정점은 인접행렬로 구성하고, 방향이 있는 그래프이니 s -> e만 배열에 저장할 것. import java.util.*; /* [백준] 1753번 - 최단경로 (Java) */ public class Main { static int V, E, K; static int[][] map; static int[] visited; .. 2022. 9. 14. [백준] 7562번 - 나이트의 이동 (Java) https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 1. BFS 탐색으로 최소이동거리를 구하는 문제이다. 2. TC가 여러개이므로 매번 맵을 초기화 해야 한다. 3. 누적거리는 map[][]에 탐색하면서 업데이트 한다. 4. 8방향으로 탐색이 가능하다. import java.util.*; /* [백준] 7562번 - 나이트의 이동 (Java) */ public class Main { static int N, M; static int map[][];.. 2022. 9. 13. [백준] 14502번 - 연구소 (Java)(△) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 1. 바이러스가 퍼지는 걸 막으려면 벽을 세워야 하는데 벽의 개수는 3개이다. 2. 바이러스가 상하좌우로 번질 수 있다고 하니 BFS에서 큐에 넣은 것은 바이러스의 위치이다. 2-1. BFS 호출 전에 for문을 돌려서 바이러스(2)를 다 큐에 넣자. 3. 이 문제는 탐색을 2번을 해야 한다. (벽 3개를 세우는 경우의 수, 바이러스 확산의 경우의 수) 3-1. 벽 3개를 완전탐색(DFS)해서 하나씩 세우다가.. 2022. 9. 12. [백준] 1697번 - 숨바꼭질 (Java) https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1. 1차원 그래프이다. 2. N의 위치에서 할 수 있는 액션은 3개이다. 2-1. nx = 2 * x 2-2. nx = x+1 2-3. nx = x - 1 3. BFS로 위 3개 액션을 for(1 to 3)문으로 돌려서 탐색한다. 4. 방문거리는 visited 배열에다가 이전거리+1을 해서 기록하고, 방문한 노드는 스킵한다. 5. N과 K가 같을 때 BFS 수행 전에 .. 2022. 9. 8. [백준] 7576번 - 토마토 (Java) https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 1. 익은 토마토는 1, 안익은 토마토는 0, 빈칸은 -1로 주어진다. 2. 익은 토마토의 상하좌우로 영향을 줘서 안익은 토마토가 하루가 지나면 익게 된다. 3. bfs 탐색으로 상하좌우로 탐색할 때 0이면 1로 바꾸고 탐색을 계속한다. 3-1. 상하좌우 검색 후에 누적거리+1 을 하자. 4. 출발점이 없으니 메인함수에서 for문을 돌려서 1이 나오면 bfs를 호출하자. 5. 0이.. 2022. 9. 7. BFS 알고리즘(너비 우선 탐색) ※ 그래프 용어 - 정점(vertex) : 그래프 안의 노드 - 간선(edge) : 각 정점을 잇는 선 - 인접(adjacent) : 간선으로 연결된 정점 - 이웃(neighbor) : 인접한 정점 BFS(Breadth First Search)로 줄여 부르는 너비 우선 탐색은 그래프를 탐색하는 방법이다. 깊이 우선 탐색과 달리 너미 우선 탐색은 재귀를 쓰지 않는다. 대신 큐로 문제를 해결한다. 큐는 FIFO로 먼저 들어간 데이터를 우선 처리한다. * 너비 우선 순회 알고리즘 1. 그래프 내 아무 정점에서 시작한다. 이 정점을 "시작 정점"이라 부른다. 2. 시작 정점을 방문 배열에 추가해 방문 표시를 한다. 3. 시작 정점을 큐에 추가한다. 4. 큐가 빌 때까지 실행하는 루프를 시작한다. 5. 루프 안에.. 2022. 9. 6. 이전 1 2 3 4 다음 반응형
