[이코테] Chapter 5. DFS, BFS (java)

📍개념

1. DFS

깊이 우선 탐색. 그래프의 깊은 부분을 우선적으로 탐색한다. 스택 or 재귀함수를 이용하여 구현.

1. 시작 노드 push, 방문 처리
2. 최상단 노드에 방문하지 않은 노드가 있다면 push, 방문 처리. 
3. 방문하지 않은 노드가 없다면 pop
4. 불가능할 때까지 2,3 반복

그래프가 위와 같고, 시작 노드가 1인 경우

탐색 순서: 1 2 7 6 8 3 4 5

import java.util.*;

public class Main {

	public static boolean[] visited = new boolean[9];
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

	public static void main(String[] args) {

		for (int i = 0; i < 9; i++)
			graph.add(new ArrayList<Integer>());

		graph.get(1).add(2);
		graph.get(1).add(3);
		graph.get(1).add(8);
		graph.get(2).add(1);
		graph.get(2).add(7);
		graph.get(3).add(1);
		graph.get(3).add(4);
		graph.get(3).add(5);
		graph.get(4).add(3);
		graph.get(4).add(5);
		graph.get(5).add(3);
		graph.get(5).add(4);
		graph.get(6).add(7);
		graph.get(7).add(2);
		graph.get(7).add(6);
		graph.get(7).add(8);
		graph.get(8).add(1);
		graph.get(8).add(7);
		dfs(1);
	}

	public static void dfs(int start) {
		visited[start] = true;
		System.out.println(start + " ");
		for (int i = 0; i < graph.get(start).size(); i++) {
			int y = graph.get(start).get(i);
			if (!visited[y])
				dfs(y);
		}
	}

}

---

2. BFS

너비 우선 탐색. 그래프에서 가까운 노드부터 우선적으로 탐색. 큐 사용하여 구현.

1. 시작 노드 push, 방문 처리
2. pop, 인접노드 중 방문하지 않은 노드 push, 방문 처리
3. 불가능할때까지 2 반복

 

 

그래프가 위와 같고, 시작 노드가 1인 경우

탐색 순서: 1 2 3 8 7 4 5 6

import java.util.*;

public class Main {

	public static boolean[] visited = new boolean[9];
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

	public static void main(String[] args) {

		for (int i = 0; i < 9; i++)
			graph.add(new ArrayList<Integer>());

		graph.get(1).add(2);
		graph.get(1).add(3);
		graph.get(1).add(8);
		graph.get(2).add(1);
		graph.get(2).add(7);
		graph.get(3).add(1);
		graph.get(3).add(4);
		graph.get(3).add(5);
		graph.get(4).add(3);
		graph.get(4).add(5);
		graph.get(5).add(3);
		graph.get(5).add(4);
		graph.get(6).add(7);
		graph.get(7).add(2);
		graph.get(7).add(6);
		graph.get(7).add(8);
		graph.get(8).add(1);
		graph.get(8).add(7);
		bfs(1);
	}

	public static void bfs(int start) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(start);
		visited[start] = true;
		while (!q.isEmpty()) {
			int x = q.poll();
			System.out.println(x + " ");
			for (int i = 0; i < graph.get(x).size(); i++) {
				int y = graph.get(x).get(i);
				if (!visited[y]) {
					q.offer(y);
					visited[y] = true;
				}
			}
		}
	}

}

---

📖 [예제 5-1] 음료수 얼려 먹기

음료수 얼려 먹기

문제

N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.
다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다

입력

• 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)
• 두 번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어진다.
• 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

출력

한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

🔑 풀이

✅ ArrayList<Integer> ice: 얼음틀의 형태를 1차원으로 저장한 리스트

✅ ArrayList<Integer> hole: 0(구멍)의 index를 저장한 리스트

✅ ArrayList<ArrayList<Integer>> graph: 얼음틀의 인접상태를저장한 리스트

✅ boolean[] visited: 방문 처리 배열

1. N, M을 입력받고, 얼음틀을 입력받는다(모든 값을 ice에, 구멍의 위치를 hole에 저장)
2. ice를 순회하며 얼음틀의 인접 상태를 graph에 저장한다 ex) {{1, 5}, {0, 2, 6} ... }
3. hole의 첫번째 원소(첫번째 구멍)와 인접한 구멍들을 bfs 함수를 이용하여 찾아 hole에서 삭제한다 ex)0과 인접한 구멍: {1, 5, 6, 7} 
4. hole이 빌 때까지 3을 반복하고 반복되는 횟수를 count한다

import java.util.*;

public class Main {
	static ArrayList<Integer> ice, hole;
	public static void main(String[] args) {
		// 입력
		Scanner scan = new Scanner(System.in);
		int N = Integer.parseInt(scan.next());
		int M = Integer.parseInt(scan.next());
		// 얼음틀 입력
		ice = new ArrayList<>();
		hole = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			String[] c = scan.next().split("");
			for (int j = 0; j < M; j++) {
				ice.add(Integer.parseInt(c[j]));
				if (c[j].equals("0")) { // 구멍의 위치를 hole에 저장
					hole.add(ice.size() - 1);
				}
			}
		}

		// 얼음틀 인접상태 저장
		ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
		for (int i = 0; i < ice.size(); i++) {
			ArrayList<Integer> link = new ArrayList<>();
			if ((i - M) >= 0) 
				link.add(i - M);
			if (((i - 1) / M) == (i / M) && i - 1 >= 0) 
				link.add(i - 1);
			if (((i + 1) / M) == (i / M)) 
				link.add(i + 1);
			if ((i + M) < (N * M)) 
				link.add(i + M);
			graph.add(link);
		}

		// bfs 방문 처리할 배열 준비
		boolean[] visited = new boolean[N * M];
		for (int i = 0; i < N * M; i++)
			visited[i] = false;

		// bfs 함수를 이용하여 구멍집합(?) 개수를 구한다
		int answer = 0;
		while (!hole.isEmpty()) {
			int h = hole.get(0);
			ArrayList<Integer> icecream = bfs(graph, h, visited);
			hole.removeAll(icecream);
			answer++;
		}

		// 결과
		System.out.println(answer);
	}
	
	// 기본 bfs 함수에 구멍인지 확인하는 절차추가 
	public static ArrayList<Integer> bfs(ArrayList<ArrayList<Integer>> graph, int start, boolean[] visited) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(start);
		visited[start] = true;

		ArrayList<Integer> icecream = new ArrayList<>();
		while (!q.isEmpty()) {
			int n = q.poll();
			icecream.add(n);
			for (int i : graph.get(n)) {
				if (!visited[i] && ice.get(i) == 0) {
					q.offer(i);
					visited[i] = true;
				}
			}
		}
		return icecream;
	}
}

첫 접근을 잘못해서 풀다가 돌아버리는줄 ㅎ bfs로 풀었습니다

 

처음에 얼음형태를 2차원 행렬로 입력받았다가 인접 그래프 만드는데 한참 고생...

겨우 만들었더니 bfs 함수에 못넣겠어서 오억시간동안 고생.....

 

결국 다 엎어버리고 1차원 리스트로 입력받고 인덱스 위치로 풀었더니 한번만에 풀림

빨리 엎을걸 ㅋ 괜히 붙잡고 있었네요....

 

근데 동빈나 선생님 풀이를 보니 아직도 이 알고리즘을 전혀 이해하지 못했구나를 깨달았습니다...

빙~빙 돌아가는 나의 풀이

import java.util.*;

public class Main {
	static int[][] ice;
	static int N, M;

	public static void main(String[] args) {
		// 입력
		Scanner scan = new Scanner(System.in);
		N = Integer.parseInt(scan.next());
		M = Integer.parseInt(scan.next());
		// 얼음틀 입력
		ice = new int[N][M];
		for (int i = 0; i < N; i++) {
			String s = scan.next();
			for (int j = 0; j < M; j++) {
				ice[i][j] = s.charAt(j) - '0';
			}
		}

		int result = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (dfs(i, j))
					result++;
			}
		}
		System.out.println(result);
	}

	public static boolean dfs(int i, int j) {

		if (i <0 || i >= N || j <0 || j >= M)
			return false;
		if (ice[i][j] == 0) {
			ice[i][j] = 1;
			dfs(i - 1, j);
			dfs(i + 1, j);
			dfs(i, j - 1);
			dfs(i, j + 1);
			return true;
		}
		return false;
	}
}

---

📖 [예제 5-2] 미로 탈출

문제

N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

입력

• 첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다. 

출력

첫째 줄에 최소 이동 칸의 개수를 출력한다.

🔑 풀이

얘는 또 dfs로 풀다가 머리가 너무 아파서 풀이 봤더니... bfs로 푸는 문제라캄 ㅋ

연습을 많이 해야할 듯 합니다...

import java.util.*;

class Nod {
	private int x;
	private int y;

	public Nod(int x, int y) {
		this.x = x;
		this.y = y;
	}

	public int getx() {
		return this.x;
	}

	public int gety() {
		return this.y;
	}
}

public class Main {
	static int[][] graph;
	static int N, M, result;
	public static int dx[] = { -1, 1, 0, 0 };
	public static int dy[] = { 0, 0, -1, 1 };

	public static void main(String[] args) {
		// 입력
		Scanner scan = new Scanner(System.in);
		N = Integer.parseInt(scan.next());
		M = Integer.parseInt(scan.next());
		graph = new int[N][M];
		for (int i = 0; i < N; i++) {
			String s = scan.next();
			for (int j = 0; j < M; j++) {
				graph[i][j] = s.charAt(j) - '0';
			}
		}

		System.out.println(bfs(0, 0));

	}

	public static int bfs(int x, int y) {
		Queue<Nod> queue = new LinkedList<>();
		queue.add(new Nod(x, y));
		
		while (!queue.isEmpty()) {
			Nod node = queue.poll();
			x = node.getx();
			y = node.gety();
			for (int i = 0; i < 4; i++) {
				// 상하좌우 이동 
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				// 벽이라면 건너뛰기 
				if (nx < 0 || nx >= N || ny < 0 || ny >= M)
					continue;
				
				// 괴물이 있는 곳도 건너뛰기 
				if (graph[nx][ny] == 0)
					continue;
				
				// 괴물이 없다면 이전 위치 값 + 1 저장 
				if (graph[nx][ny] == 1) {
					graph[nx][ny] = graph[x][y] + 1;
					queue.offer(new Nod(nx, ny));
				}
			}
		}
		
		// N,M 위치 값 return 
		return graph[N - 1][M - 1];
	}
}