R x C 직사각형 모양의 호수가 존재한다. 이 호수에는 백조가 두 마리 존재하는데 빙판이 있어 서로 만날 수 없다. 하루가 지날 때마다 물에 인접한 빙판들은 모두 녹는다고 할 때 며칠이 지나야 백조 두 마리가 만날 수 있는지 구하시오.
2.문제예제
3.문제풀이(수동)
전형적인 BFS 문제로 수동 풀이는 진행하지 않는다. 지문에서 언급한 내용처럼 물에 인접한 빙판들은 모두 녹는다.
녹을 때 두 백조가 만날 수 있는지만 체크하면 된다.
4.팩트추출
Fact 1: 전형적인 BFS 문제이다. 한 번 맵을 훑으면서 빙판을 녹이고, 백조가 서로 만나는지 다시 맵을 훑으면 된다. 단순 BFS 구현 문제라고 생각이 들지만, R 과 C 가 무려 1500 으로 한 번 맵을 탐색할 때마다 1500 * 1500 시간복잡도가 발생한다. 그것도 빙판을 녹일 때 한 번, 백조가 서로 만나는지 확인하기 위해 한 번 수행하면 총 1500 * 1500 * 2 시간복잡도가 된다. 조금 더 효과적으로 BFS 를 수행해야 한다.
Fact 2:백조 중심으로 BFS 를 수행하면 빙판을 만나거나 백조를 만나거나 두 가지 경우를 만나게 된다. 백조를 만나면 그 동안에 계산된 day 를 리턴하면 되고, 빙판을 만났다면 그 빙판들을 기억하기 위해 모두 큐에 담아 그 큐에서부터 다시 시작하면 된다. 빙판을 녹이기 위한 BFS 는 따로 수행해서 서로 영향을 미치지 않게 동작시킨다. 따라서, Water 에 대한 큐, 다음 검색을 위한 큐가 필요하다.
5.문제전략
문제 전략은 팩트 추출을 통해 알아보았다. 백조 중 하나부터 시작해서 dfs 를 수행하고 빙판을 만나면 그 지점들을 기억했다가 다시 그 부분부터 dfs 를 시작하면 된다. 다시 dfs 를 시작하기 전 빙판이 녹아야 하므로 빙판에 대한 dfs 를 한 번 수행한다.
6.소스코드
package org.example;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int R, C;
private static Node[] swan;
private static char[][] map;
private static Queue<Node> queue, waterQueue;
private static boolean[][] visited;
private static final int[] dr = { -1, 1, 0, 0 };
private static final int[] dc = { 0, 0, -1, 1 };
private static int day = 0;
static class Node {
int r, c;
Node(int r, int c) {
this.r = r;
this.c = c;
}
}
private static void waterBFS() {
// 한 번만 녹여야 하므로, 현재 큐 사이즈만큼만 돌린다.
int waterSize = waterQueue.size();
while (waterSize-- > 0) {
Node now = waterQueue.poll();
for (int i = 0; i < 4; i++) {
int nextR = now.r + dr[i];
int nextC = now.c + dc[i];
if (nextR >= R || nextR < 0 || nextC >= C || nextC < 0) continue;
if (map[nextR][nextC] == 'X') {
map[nextR][nextC] = '.';
waterQueue.offer(new Node(nextR, nextC));
}
}
}
}
private static void BFS() {
boolean meet = false;
while (true) {
Queue<Node> nextQueue = new LinkedList<>();
while (!queue.isEmpty()) {
Node now = queue.poll();
if (now.r == swan[1].r && now.c == swan[1].c) {
meet = true;
break;
}
for (int i = 0; i < 4; i++) {
int nextR = now.r + dr[i];
int nextC = now.c + dc[i];
if (nextR >= R || nextR < 0 || nextC >= C || nextC < 0 || visited[nextR][nextC]) continue;
visited[nextR][nextC] = true;
if (map[nextR][nextC] == 'X') {
nextQueue.offer(new Node(nextR, nextC));
continue;
}
queue.offer(new Node(nextR, nextC));
}
}
if (meet) break;
queue = nextQueue;
waterBFS();
day++;
}
return;
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new char[R][C];
swan = new Node[2];
queue = new LinkedList<>();
waterQueue = new LinkedList<>();
visited = new boolean[R][C];
int swanIndex = 0;
for (int i = 0; i < R; i++) {
char[] line = br.readLine().toCharArray();
for (int j = 0; j < C; j++) {
map[i][j] = line[j];
if(map[i][j] == 'L') {
swan[swanIndex++] = new Node(i, j);
}
if(map[i][j] != 'X') {
waterQueue.offer(new Node(i, j));
}
}
}
queue.offer(swan[0]);
visited[swan[0].r][swan[0].c] = true;
BFS();
System.out.println(day);
}
}
각 문제마다 조건이 추가된다. 이 N 과 M 시리즈는 재귀함수(DFS)의 본질을 이해하고, 우리가 흔히 접할 수 있는 순열 및 조합 문제를 풀 수 있는 기초가 되기 때문에 꼭 풀어보는 것을 권장한다.
N과 M (1)
+ 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
+ 자기 자신은 제외하고 남은 수열을 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations;
private static boolean[] visited;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
for (int i = 0; i < N; i++) {
if (!visited[i]) {
combinations[depth] = i + 1;
visited[i] = true;
dfs(i, depth + 1);
visited[i] = false;
}
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
combinations = new int[N];
visited = new boolean[N];
dfs(0,0);
System.out.println(sb.toString());
}
}
N과 M (2)
+ 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations;
private static boolean[] visited;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
for (int i = index; i < N; i++) {
if (!visited[i]) {
combinations[depth] = i + 1;
visited[i] = true;
dfs(i, depth + 1);
visited[i] = false;
}
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
combinations = new int[N];
visited = new boolean[N];
dfs(0,0);
System.out.println(sb.toString());
}
}
N과 M (3)
+ 1부터 N까지 자연수 중에서 M개를 고른 수열
+ 같은 수를 여러 번 골라도 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
for (int i = 0; i < N; i++) {
combinations[depth] = i+1;
dfs(i, depth + 1);
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
combinations = new int[N];
dfs(0,0);
System.out.println(sb.toString());
}
}
N과 M (4)
+ 1부터 N까지 자연수 중에서 M개를 고른 수열
+ 같은 수를 여러 번 골라도 된다.
+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
for (int i = index; i < N; i++) {
combinations[depth] = i+1;
dfs(i, depth + 1);
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
combinations = new int[N];
dfs(0,0);
System.out.println(sb.toString());
}
}
N과 M (5)
+ 자기 자신은 제외하고 남은 수열을 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations, items;
private static boolean[] visited;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
for (int i = 0; i < N; i++) {
if(!visited[i]) {
combinations[depth] = items[i];
visited[i] = true;
dfs(i, depth + 1);
visited[i] = false;
}
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
items = new int[N];
combinations = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
items[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(items);
visited = new boolean[N];
dfs(0,0);
System.out.println(sb.toString());
}
}
N과 M (6)
+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations, items;
private static boolean[] visited;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
for (int i = index; i < N; i++) {
if(!visited[i]) {
combinations[depth] = items[i];
visited[i] = true;
dfs(i, depth + 1);
visited[i] = false;
}
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
items = new int[N];
combinations = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
items[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(items);
visited = new boolean[N];
dfs(0,0);
System.out.println(sb.toString());
}
}
N과 M (7)
+ 같은 수를 여러 번 골라도 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations, items;
private static boolean[] visited;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
for (int i = 0; i < N; i++) {
combinations[depth] = items[i];
dfs(i,depth + 1);
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
items = new int[N];
combinations = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
items[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(items);
dfs(0,0);
System.out.println(sb.toString());
}
}
N과 M (8)
+ 같은 수를 여러 번 골라도 된다.
+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations, items;
private static boolean[] visited;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
for (int i = index; i < N; i++) {
combinations[depth] = items[i];
dfs(i,depth + 1);
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
items = new int[N];
combinations = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
items[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(items);
dfs(0,0);
System.out.println(sb.toString());
}
}
N과 M (9)
+ 중복 수열은 출력하지 않는다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations, items;
private static boolean[] visited;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
int prevNumber = -1;
for (int i = 0; i < N; i++) {
if (prevNumber != items[i] && !visited[i]) {
combinations[depth] = items[i];
prevNumber = items[i];
visited[i] = true;
dfs(depth + 1);
visited[i] = false;
}
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
items = new int[N];
combinations = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
items[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(items);
visited = new boolean[N];
dfs(0);
System.out.println(sb.toString());
}
}
N과 M (10)
+ 같은 수를 여러 번 골라도 된다.
+ 중복 수열은 출력하지 않는다.
+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations, items;
private static boolean[] visited;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
int prevNumber = -1;
for (int i = index; i < N; i++) {
if (prevNumber != items[i] && !visited[i]) {
combinations[depth] = items[i];
prevNumber = items[i];
visited[i] = true;
dfs(i, depth + 1);
visited[i] = false;
}
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
items = new int[N];
combinations = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
items[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(items);
visited = new boolean[N];
dfs(0, 0);
System.out.println(sb.toString());
}
}
N과 M (11)
+ 같은 수를 여러 번 골라도 된다.
+ 중복 수열은 출력하지 않는다.
+ 같은 숫자를 여러 번 골라도 된다.
package org.example;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations, items;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
int prevNumber = -1;
for (int i = 0; i < N; i++) {
if (prevNumber != items[i]) {
combinations[depth] = items[i];
prevNumber = items[i];
dfs(i, depth + 1);
}
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
items = new int[N];
combinations = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
items[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(items);
dfs(0, 0);
System.out.println(sb.toString());
}
}
N과 M (12)
+ 같은 수를 여러 번 골라도 된다.
+ 중복 수열은 출력하지 않는다.
+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations, items;
private static List<Integer> itemsDistinct;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
int prevNumber = -1;
for (int i = index; i < N; i++) {
if (prevNumber != items[i]) {
combinations[depth] = items[i];
prevNumber = items[i];
dfs(i, depth + 1);
}
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
items = new int[N];
combinations = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
items[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(items);
dfs(0, 0);
System.out.println(sb.toString());
}
}
지도의 각 칸에는 그 지점의 높이가 주어지며 (0, 0) 지점에서 (n-1, m-1) 지점으로 내려가려고 한다. 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 할 때 이동할 수 있는 경로의 수를 구하시오.
2.문제예제
3.팩트추출
Fact 1:전형적인 BFS 와 DFS 문제인것처럼보이지만, 입력의범위를보면완전탐색시시간초과가발생할수있다. 최대칸수가 500 * 500 으로 250000 이며상하좌우 4방향으로움직일수있으니 4 의 250000 제곱경우의수가존재한다. 경우의수를줄일수있는방법을찾아야한다.
Fact 2: 문제예제를살펴보면전체문제의답이작은부분문제의답의합으로구성되어있다. 50 번지점에서 목적지까지가는경로의수는 45번지점에서가는경로의수 + 35번지점에서 가는경로의수로이루어져있다. 35번지점이나 30번지점, 27번 지점은경로의수가하나로나중에이지점을방문하더라도계산할필요가없다. 즉 DP 문제이다.
Fact 3 : 기존 DFS 나 BFS 에서사용하던 visited 배열을응용하여 "해당지점에서목적지까지가는경로의수" 로생각하여해당값을재활용하면탐색범위를줄일수있다. 여기서중요한점은 DFS 와 BFS 의 visited 배열활용도가조금다르다는 것이다. BFS 는주변부터탐색하기때문에단순방문했는지여부만파악할수있지만 DFS 는한가지경우의수부터모두탐색하고다시원래위치로돌아오기때문에수행도중 visited 배열을오염시킨다면 그경로는다시탐색하지않아도된다. 4 번 문제 풀이 (수동) 부분에서 자세히 확인한다.
Fact 4: DP[x][y] 배열을 0 으로 초기화하면 이 경로의 수가 0 인지 노드를 방문하지 않은 것인지 확인이 불가능하다. DP 배열이 visited 배열의 역할도 하기 때문에 -1 로 초기화한다.
4.문제풀이(수동)
문제 예제 입력 1을 DFS 알고리즘 + DP 방식으로 문제를 풀었을 때 애니메이션이다.
손수 애니메이션으로 만들어준 우투리와툴툴 티스토리 블로그님께 감사의 말씀을 전한다. 덕분에 이해하기가 쉽다.
5.문제전략
문제 전략은 팩트 추출을 통해 알아보았다. DFS + DP 방식으로 문제를 풀었다.
6.소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int M, N;
static int[][] map;
static int[][] dp;
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, 1, -1 };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = new int[M][N];
dp = new int[M][N];
for(int j = 0; j < M; j++) {
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
map[j][i] = Integer.parseInt(st.nextToken());
}
}
initDP();
System.out.println(dfs(0, 0));
}
private static void initDP() {
for(int j = 0; j < M; j++) {
for (int i = 0; i < N; i++) {
dp[j][i] = -1;
}
}
}
private static int dfs(int x, int y) {
if(x == M-1 && y == N-1){ return 1; }
if(dp[x][y] != -1) return dp[x][y];
dp[x][y] = 0;
for (int i=0; i<4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (newX < 0 || newX >= M || newY < 0 || newY >= N) continue;
if (map[x][y] <= map[newX][newY]) continue;
dp[x][y] += dfs(newX, newY);
}
return dp[x][y];
}
}
BFS 알고리즘은 넓이 우선 탐색 알고리즘이며, DFS 알고리즘은 깊이우선탐색 알고리즘이다.
<템플릿>
public static void bfs(int start) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
// 현재 노드를 방문 처리
visited[start] = true;
// 큐가 빌 때까지 반복
while(!q.isEmpty()) {
// 큐에서 하나의 원소를 뽑아 출력
int x = q.poll();
// 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for(int i = 0; i < graph.get(x).size(); i++) {
int y = graph.get(x).get(i);
// if 제어문의 반복
// if(visited[y]) continue;
q.offer(y);
visited[y] = true;
}
}
}
public static void dfs(int x) {
// 현재 노드를 방문 처리
visited[x] = true;
System.out.print(x + " ");
// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for (int i = 0; i < graph.get(x).size(); i++) {
int y = graph.get(x).get(i);
if (!visited[y]) dfs(y);
}
}
