BFS / DFS
개념
BFS : Breadth First Search
-> 근처(인접한)에 있는 것부터 찾는 알고리즘
-> Queue 이용
DFS : Depth First Search
-> 깊이 우선 순위 탐색
-> Stack 이용
문제
1. Basic_BFS
문자 1, 0으로 이루어진 char[][] 배열이 주어졌고, 1은 육지, 0은 바다라 했을 때 육지의 갯수를 반환
Input : char[][] map {
{'1', '1', '0', '0', '1'},
{'1', '1', '0', '0', '0'},
{'0', '0', '0', '0', '0'},
{'0', '0', '0', '1', '1'}
}
Output : 3
풀이
- '1'일 때 count +1 를 해준다.
- '1'를 만난 좌표 기준으로 상, 하, 좌, 우 를 살펴 0으로 만들어준다.
- map 이 0으로 될 때까지 1~2과정을 반복
외워야하는 부분
1. 맞는 조건을 찾아내는 부분
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == '1') {
count += 1;
bfs(map, i, j);
}
}
}2. 방향 설정 과 이차원 배열 사이즈
public static int m, n;
// 상, 하, 좌, 우
public static int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 } };
m = map.length;
n = map[0].length;
3. 큐에서 빼는 부분
Queue<int[]> q = new LinkedList<int[]>();
q.offer(new int[] { x, y });
while (!q.isEmpty()) {
int[] point = q.poll();
for (int[] dir : dirs) {
int nx = point[0] + dir[0];
int ny = point[1] + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && map[nx][ny] == '1') {
map[nx][ny] = '0';
q.offer(new int[] { nx, ny });
}
}
}4. 조건을 확인해서 큐에 다시 넣는 부분
4.1) 상,하,좌,우로 이동했을 때 좌표의 범위
4.2) map[x][y]의 값 확인 -> 문제에서 '1'에 해당하는 부분인지
if (nx >= 0 && nx < m && ny >= 0 && ny < n && map[nx][ny] == '1') {
map[nx][ny] = '0';
q.offer(new int[] { nx, ny });
}소스 - 강의 버전
import java.util.*;
public class Q1 {
// 상, 하, 좌, 우
public static int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 } };
public static void main(String[] args) {
char[][] map = {
{ '1', '1', '0', '0', '1' },
{ '1', '1', '0', '0', '0' },
{ '0', '0', '0', '0', '0' },
{ '0', '0', '0', '1', '1' }
};
System.out.println(solve(map));
}
public static int solve(char[][] map) {
if (map == null || map.length == 0) {
return 0;
}
int count = 0;
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
if (map[i][j] == '1') {
count += 1;
bfs(map, i, j);
}
}
}
return count;
}
public static void bfs(char[][] map, int x, int y) {
Queue<int[]> q = new LinkedList<int[]>();
q.offer(new int[] { x, y });
while (!q.isEmpty()) {
int[] point = q.poll();
for (int[] dir : dirs) {
int nx = point[0] + dir[0];
int ny = point[1] + dir[1];
if (nx >= 0 && nx < map.length && ny >= 0 && ny < map[0].length && map[nx][ny] == '1') {
map[nx][ny] = '0';
q.offer(new int[] { nx, ny });
}
}
}
}
}소스 - 필자 버전
차이점 : 방향을 int[] dx, int[] dy를 만들어서 사용하고, 좌표를 저장하는 객체를 만들어서 사용함
import java.util.*;
class Point {
private int x;
private int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
}
public class Q1_min {
public static int m, n;
// 상, 하, 좌, 우
public static int[] dx = { 1, -1, 0, 0 };
public static int[] dy = { 0, 0, -1, 1 };
public static void main(String[] args) {
char[][] map = { { '1', '1', '0', '0', '1' }, { '1', '1', '0', '0', '0' }, { '0', '0', '0', '0', '0' },
{ '0', '0', '0', '1', '1' } };
System.out.println(solve(map));
}
public static int solve(char[][] map) {
if (map == null || map.length == 0) {
return 0;
}
int count = 0;
m = map.length;
n = map[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == '1') {
count += 1;
bfs(map, i, j);
}
}
}
return count;
}
public static void bfs(char[][] map, int x, int y) {
Queue<Point> q = new LinkedList<Point>();
q.offer(new Point(x, y));
while (!q.isEmpty()) {
Point p = q.poll();
x = p.getX();
y = p.getY();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && map[nx][ny] == '1') {
map[nx][ny] = '0';
q.offer(new Point(nx, ny));
}
}
}
}
}2. Basic_DFS
- Basic_BFS 문제와 동일
풀이
- Basic_BFS와 동일
- DFS형태로 바꿔서 풀면 된다.
외워야하는 부분
1. 맞는 조건을 찾아내는 부분
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == '1') {
count += 1;
dfs(map, i, j);
}
}
}2. 방향 설정 과 이차원 배열 사이즈
public static int m, n;
// 상, 하, 좌, 우
public static int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 } };
m = map.length;
n = map[0].length;
3. 재귀를 이용하는 부분 (stack 개념)
public static void dfs(char[][] map, int x, int y) {
if (x < 0 || y < 0 || x >= m || y >= n || map[x][y] != '1') {
return;
}
map[x][y] = '0';
for (int[] dir : dirs) {
dfs(map, x + dir[0], y + dir[1]);
}
// dfs(map, x + 1, y); // 상
// dfs(map, x - 1, y); // 하
// dfs(map, x, y - 1); // 좌
// dfs(map, x, y + 1); // 우
}4. 조건을 확인하는 부분
4.1) 상,하,좌,우로 이동했을 때 좌표의 범위를 벗어나는지
4.2) map[x][y]의 값이 '1'이 아닌지
-> 재귀를 이용하기 때문에 위 조건이 아닐때 반환하는 형태로 구현 (중요)
if (x < 0 || y < 0 || x >= m || y >= n || map[x][y] != '1') {
return;
}소스
public class Q2 {
public static int m, n;
public static int[][] dirs = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
public static void main(String[] args) {
char[][] map = {
{ '1', '1', '0', '0', '0' },
{ '1', '1', '0', '0', '0' },
{ '0', '0', '1', '0', '0' },
{ '0', '0', '0', '1', '1' } };
System.out.println(solve(map));
}
public static int solve(char[][] map) {
// error check
if (map == null || map.length == 0 || map[0].length == 0) {
return 0;
}
m = map.length;
n = map[0].length;
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == '1') {
count += 1;
dfs(map, i, j);
}
}
}
return count;
}
public static void dfs(char[][] map, int x, int y) {
if (x < 0 || y < 0 || x >= m || y >= n || map[x][y] != '1') {
return;
}
map[x][y] = '0';
for (int[] dir : dirs) {
dfs(map, x + dir[0], y + dir[1]);
}
// dfs(map, x + 1, y); // 상
// dfs(map, x - 1, y); // 하
// dfs(map, x, y - 1); // 좌
// dfs(map, x, y + 1); // 우
}
}
3. BFS 응용 문제
트리가 주어졌을 때 BFS를 이용하여 각 노드의 값을 출력
Input :
Output : [[1], [3,2], [4,5]]
풀이
- TreeNode를 저장하는 Queue를 선언하고 root 노드를 offer한다.
- 큐가 빌때까지 하나씩 꺼내서 List에 넣는다.
- 이때 [2,3] -> [3,2]로 들어가게 하기 위해 boolean 변수를 사용한다.
- 그 후에 해당 노드에 왼쪽과 오른쪽에 노드가 존재하면 큐에 넣는다.
소스
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) {
this.val = val;
}
}
public class Q3 {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
System.out.println(solve(root));
}
public static List<List<Integer>> solve(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
Queue<TreeNode> q = new LinkedList<TreeNode>();
boolean zigzag = true;
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
//System.out.println("node.val : " + node.val);
//System.out.println("zigzag : " + zigzag);
if (zigzag) {
list.add(node.val);
} else {
list.add(0, node.val);
}
if (node.left != null) {
q.offer(node.left);
}
if (node.right != null) {
q.offer(node.right);
}
}
zigzag = !zigzag;
result.add(list);
}
return result;
}
}4. DFS 응용 문제
matrix가 주어졌을 때 가장 긴 증가하는 경로를 찾아 그 길이를 반환
(같은 수는 포함하면 안됨)Input : matrix =
[[9,8,3],
[6,5,7],
[2,1,1]]
Output : 4
설명)
result = [
[1,2,3],
[2,3,1],
[3,4,0]
]
따라서 1 -> 2 -> 6 -> 9 혹은 1-> 5 -> 8 -> 9 가능하고 제일 긴 길이는 4
풀이
- 이 문제는 DFS를 이용하면서 memoization 을 활용해야 한다. 왜냐하면 각 위치에서의 최대 길이를 저장해야 원하는 값을 구할 수 있기 때문이다.
- (0,0) 위치부터 시작하여 길이를 구한 뒤 max와 비교하여 큰 값으로 max를 갱신한다.
- 상,하,좌,우 4 방향으로 for문을 돌리면서 조건에 맞을 때 dfs를 호출하면서 길이의 +1를 해주고 max를 갱신한다.
- memoization을 하는 result 배열에서 해당 위치에 max값을 넣어준다.
소스
public class Q4 {
public static int m, n;
// 상 하 좌 우
public static int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
public static void main(String[] args) {
int[][] grid = { { 9, 8, 3 }, { 6, 5, 7 }, { 2, 1, 1 } };
System.out.println(solve(grid));
}
public static int solve(int[][] grid) {
if (grid.length == 0) {
return 0;
}
m = grid.length;
n = grid[0].length;
int[][] result = new int[m][n];
int max = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int len = dfs(grid, i, j, result);
max = Math.max(max, len);
}
}
return max;
}
public static int dfs(int[][] grid, int i, int j, int[][] result) {
if (result[i][j] != 0) {
return result[i][j];
}
int max = 1;
for (int[] dir : dirs) {
int x = i + dir[0];
int y = j + dir[1];
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] <= grid[i][j]) {
continue;
}
int len = 1 + dfs(grid, x, y, result);
max = Math.max(max, len);
}
result[i][j] = max;
return max;
}
}5. BFS응용문제 count_areaSize 구하기
1번 문제인 Basic_BFS에서 응용하는 문제이다.
주어진 2차원 배열에서 영역의 갯수와 그 영역의 길이 중 최대값을 출력
Input : int[][] grid = {
{ 0, 0, 3, 3 },
{ 1, 4, 0, 1 },
{ 1, 0, 0, 1 },
{ 1, 0, 0, 1 },
{ 1, 2, 2, 0 },
{ 1, 1, 0, 0 } };
Output : [5,6]
풀이
- Basic_BFS의 기본 틀에서 몇가지의 코드만 추가하면 된다.
- 방문을 하지 않고 0이 아닐 때 count+1를 해주고 해당 부분의 길이를 구하면 된다.
- 해당 부분의 길이를 구할 때 bfs를 이용하면 되는데 큐를 선언하여 큐에서 하나씩 뺄때마다 길이 +1 를 해준다.
- 다시 큐에 넣을 때는 범위를 벗어나지 않으면서 방문하지 않고, 이전 값과 동일할 때 큐에 넣어준다.
소스
import java.util.*;
public class Q5 {
public static int m, n;
public static boolean[][] visited;
// 상 하 좌 우
public static int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
public static void main(String[] args) {
int[][] grid = {
{ 0, 0, 3, 3 },
{ 1, 4, 0, 1 },
{ 1, 0, 0, 1 },
{ 1, 0, 0, 1 },
{ 1, 2, 2, 0 },
{ 1, 1, 0, 0 } };
System.out.println(Arrays.toString(solve(grid)));
}
public static int[] solve(int[][] grid) {
int maxSize = 0;
m = grid.length;
n = grid[0].length;
visited = new boolean[m][n];
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (visited[i][j] || grid[i][j] == 0) {
continue;
}
count++;
int thisAreaSize = bfs(grid, i, j);
maxSize = Math.max(maxSize, thisAreaSize);
}
}
int[] result = new int[2];
result[0] = count;
result[1] = maxSize;
return result;
}
public static int bfs(int[][] grid, int i, int j) {
Queue<int[]> q = new LinkedList<int[]>();
q.offer(new int[] { i, j });
visited[i][j] = true;
int thisAreaSize = 0;
while (!q.isEmpty()) {
int[] point = q.poll();
thisAreaSize++;
for (int[] dir : dirs) {
int nx = point[0] + dir[0];
int ny = point[1] + dir[1];
if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
if (!visited[nx][ny] && grid[i][j] == grid[nx][ny]) {
q.offer(new int[] { nx, ny });
visited[nx][ny] = true;
}
}
}
}
return thisAreaSize;
}
}참고
인프런 강의 : 코딩테스트 전 꼭 알아야 할 개념과 문제(with 자바) - 푸샵맨 코딩스터디
