목록BFS (24)
Dev.baelanche
[백준 2206] 벽 부수고 이동하기
2차원 배열에서 BFS 를 순회하는데 벽을 한 번 부술 수 있다. 방문 정보 배열을 2층으로 구성하여 벽을 부수고 지나갔을 때의 정보와 벽을 안부쉈을때의 정보를 따로 기록한다. 큐에도 벽 부수기에 대한 정보를 담아 한번 부수면 더이상 부술수 없게 한다. public class Main { static int n; static int m; static int a[][]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); a = new int[n][m]; for(int i=0; i
[백준 3055] 탈출
이 문제와 로직이 같은 문제이다. public class Main { static int r; static int c; static char a[][]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); r = sc.nextInt(); c = sc.nextInt(); a = new char[r][c]; for(int i=0; i
[백준 5427] 불
빠른 시간이므로 BFS 로 접근해야한다. 시간이 지날때마다 사람의 이동, 불의 이동이 이루어지므로 큐를 따로 만들어 사용한다. 처음에는 사람 이동 -> 불 이동 순으로 구현했었는데 예제는 모두 통과하는데도 틀리다고 나왔다. 문제에 불이 옮겨옴과 동시에 이동할 수 있다는 구문을 보고 불 이동 -> 사람 이동 으로 순서를 바꾸었더니 통과했다. 불이 먼저 이동해서 사람 위치를 차지하면 사람이 안움직일줄 알았는데 이미 큐에 담겨있어서 움직일 수 있었다. # # . # # # # . # # 사람 사람 . 불 불 사람 # # # 불 사람 # # # 불 왜 틀렸는지에 대한 예제를 생각해냈다. 사람, 불은 빨간 위치에서 시작하고 현재 3칸씩 이동한 상황이다. 사람 -> 불 순으로 이동하면 사람이 (3, 3) 으로 이동..
[백준 6593] 상범 빌딩
최단 시간을 구해야하므로 BFS 로 접근한다. 지나갈 수 있는 길을 탐색하면 되는데 배열이 3차원이라는 데에 주의해야 한다. S . . . . # # # # # # # # # # . # # # . # # # # # # # # # # . # # . . # # . # # # . # # # # # # . # # # . . . # # # # E 예제로 풀이해보자. 왼쪽부터 1, 2, 3층이다. S . . . . # # # # # # # # # # . # # # . # # # # # # # # # # . # # . . # # . # # # . # # # # # # . # # # . . . # # # # E 한칸 이동했을때이다. 가까운 동서남북상하로 이동했다. S . . . . # # # # # # # # # # ..
[백준 7562] 나이트의 이동
BFS 로 인접노드 탐색을 하는 문제다. 나이트는 날일 자로 이동하기 때문에 이 부분만 기억하고 풀면된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); int mx[] = {-1, 1, 2, 2, 1, -1, -2, -2}; int my[] = {2, 2, 1, -1, -2, -2, -1, 1}; while(t-->0) { int l = sc.nextInt(); boolean visited[][] = new boolean[l][l]; int jump[][] = new int[l][l]; Queue q = new LinkedList(); ..
[백준 2178] 미로 탐색
BFS 로 인접노드탐색을 하면 된다. DFS 로도 구현을 할 수는 있는데 노드 레벨 순서대로 타는 것이 아니기 때문에 시간이 너무 오래걸리게 된다. public class Main { static int n; static int m; static int a[][] = new int[100][100]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); for(int i=0; i
[백준 2644] 촌수계산
BFS 로 노드 a 에서 b 까지의 레벨을 구하는 문제이다. 너비 탐색 기법을 쓸 줄만 안다면 충분히 풀 수 있다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int arr[][] = new int[101][101]; boolean visited[] = new boolean[101]; Queue q = new LinkedList(); int a = sc.nextInt(); int b = sc.nextInt(); int m = sc.nextInt(); while(m-->0) { int x = sc.nextInt(); int y = sc...
[백준 1260] DFS와 BFS
노드의 간선의 정보를 받아 DFS, BFS 로 구현한다. 1. 그래프 형태로 정보를 받아 저장한다. 2. visited 배열을 만들어 방문 이력을 기록한다. 3. DFS 및 BFS 를 구현한다. public class Main { static int n; static int m; static int a[][]; static boolean visited[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); a = new int[n+1][n+1]; visited = new boolean[n+1]; int V = sc.nextInt(); for(int i=..