[백준] java 알고리즘 스터디 - DFS/BFS

2178 미로 탐색

📌문제 링크

https://www.acmicpc.net/problem/2178

💡 문제 풀이

📋코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	// 이동 delta 배열
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] line = br.readLine().split(" ");
		int N = Integer.parseInt(line[0]);
		int M = Integer.parseInt(line[1]);
		
		int[][] map = new int[N][M];
		
		for (int i = 0; i < N; i++) {
			String tmp = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = tmp.charAt(j) - '0';
			}
		}
		
        // BFS
		Queue<int[]> queue = new ArrayDeque<int[]>();
		queue.offer(new int[] {0, 0, 1}); // x, y, 이동한 칸의 수
		
		while(!queue.isEmpty()) {
			int[] cur = queue.poll();
            
            // (N, M)에 도착하면 종료
			if (cur[0] == N-1 && cur[1] == M-1) {
				System.out.println(cur[2]);
				break;
			}
			
            // 상하좌우 이동
			for (int i = 0; i < 4; i++) {
				int nx = cur[0] + dx[i];
				int ny = cur[1] + dy[i];
				
				if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
				if (map[nx][ny] != 1) continue;
				
                // map에 방문 표시
				map[nx][ny] = -1;
				queue.add(new int[] {nx, ny, cur[2]+1});
			}
			
		}
		
	}

}

⏱ 시간 복잡도

입력 : O(N*M)
BFS : O(N*M)
-> 시간복잡도 : O(N*M)

2606 바이러스

📌문제 링크

https://www.acmicpc.net/problem/2606

💡 문제 풀이

📋코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
        // 인접행렬
		boolean[][] adj = new boolean[N+1][N+1];
        // 방문 배열
		boolean[] visited = new boolean[N+1];
		
		for (int i = 0; i < M; i++) {
			String[] tmp = br.readLine().split(" ");
			int a = Integer.parseInt(tmp[0]);
			int b = Integer.parseInt(tmp[1]);
			
			adj[a][b] = true;
			adj[b][a] = true;
		}
		
        // BFS
		Queue<Integer> queue = new ArrayDeque<Integer>();
		queue.offer(1);
		visited[1] = true;
		
        // 1번 컴퓨터와 연결된 컴퓨터 개수
		int cnt = 0;
		while(!queue.isEmpty()) {
			int cur = queue.poll();
			
			for (int i = 1; i <= N; i++) {
				if (adj[cur][i] && !visited[i]) {
					queue.offer(i);
					visited[i] = true;
					cnt++;
				}
			}
		}
		
		System.out.println(cnt);
		
	}

}

⏱ 시간 복잡도

입력 : O(M)
BFS : O(N*N)

11725 트리의 부모 찾기

📌문제 링크

https://www.acmicpc.net/problem/11725

💡 문제 풀이

N의 최댓값이 100,000이고, 간선 개수의 최댓값이 99,999이므로 인접리스트를 사용했다.

📋코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
        // 인접리스트
		ArrayList<ArrayList<Integer>> adj = new ArrayList<>(N+1);
		for (int i = 0; i < N+1; i++) {
			adj.add(new ArrayList<>());
		}
		
		String[] tmp;
		int v, u;
		for (int i = 0; i < N-1; i++) {
			tmp = br.readLine().split(" ");
			v = Integer.parseInt(tmp[0]);
			u = Integer.parseInt(tmp[1]);
			
			adj.get(v).add(u);
			adj.get(u).add(v);
			
		}
		
		// BFS
		Queue<Integer> queue = new ArrayDeque<Integer>();
        // 방문 배열
		boolean[] visited = new boolean[N+1];
		queue.offer(1);
		visited[1] = true;
		
        // 부모 노드 배열
		int[] parent = new int[N+1];
		while(!queue.isEmpty()) {
			int cur = queue.poll();
			
            // 자식으로 이동
			for (int ad : adj.get(cur)) {
				if (!visited[ad]) {
					visited[ad] = true;
					queue.offer(ad);
                    // 현재 노드 값이 다음 이동할 노드의 부모
					parent[ad] = cur;
				}
			}
		}
		
        // 2번 노드부터 부모 노드의 번호 출력
		StringBuilder sb = new StringBuilder(N-2);
		for (int i = 2; i <= N; i++) {
			sb.append(parent[i]).append("\n");
		}
		
		System.out.print(sb);
	}

}

⏱ 시간 복잡도

입력 : O(N)
BFS : 인접리스트 시간복잡도 O(V+E) -> O(N+N-1) => O(N)
출력 : O(N)
-> O(N)

4963 섬의 개수

📌문제 링크

https://www.acmicpc.net/problem/4963

💡 문제 풀이

📋코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	// 상하좌우 + 대각선 이동 delta 배열
	static int[] dx = {-1, 1, 0, 0, 1, 1, -1, -1};
	static int[] dy = {0, 0, -1, 1, 1, -1, 1, -1};
	static int[][] map;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		StringBuilder sb = new StringBuilder();
		
		while (true) {
			stk = new StringTokenizer(br.readLine());
			int w = Integer.parseInt(stk.nextToken());
			int h = Integer.parseInt(stk.nextToken());
			
            // 0 0이 입력으로 주어지면 종료
			if (w == 0 && h == 0) break;
			
            // 지도 입력
            // 배열 범위 검사를 하지 않아도 되도록 지도의 가장자리를 0으로 채움 
            // -> [h+2][w+2]의 범위만큼 배열 선언
			map = new int[h+2][w+2];
			for (int i = 1; i <= h; i++) {
				stk = new StringTokenizer(br.readLine());
				for (int j = 1; j <= w; j++) {
					map[i][j] = Integer.parseInt(stk.nextToken());
				}
			}
			
			int cnt = 0; // 섬의 개수
            // 정사각형을 만나면 bfs 시작
			for (int i = 1; i <= h; i++) {
				for (int j = 1; j <= w; j++) {
					if (map[i][j] == 1) {
						bfs(i, j);
                        // bfs로 이어져 있는 사각형 탐색을 끝내면 한 섬을 탐색한 것
						cnt++;
					}
				}
			}
			
			sb.append(cnt).append("\n");
		}
		System.out.print(sb);
	}

	private static void bfs(int x, int y) {
		Queue<int[]> queue = new ArrayDeque<int[]>();
		queue.offer(new int[] {x, y});
        // map 배열에 방문 체크
		map[x][y] = -1;
		
		while(!queue.isEmpty()) {
			int[] cur = queue.poll();
			
			for (int i = 0; i < 8; i++) {
				int nx = cur[0] + dx[i];
				int ny = cur[1] + dy[i];
				
				if (map[nx][ny] == 1) {
					map[nx][ny] = -1;
					queue.offer(new int[] {nx, ny});
				}
			}
			
		}
	}

}

⏱ 시간 복잡도

2468 안전 영역

📌문제 링크

https://www.acmicpc.net/problem/2468

💡 문제 풀이

비가 내린 뒤 아무 곳도 잠기지 않은 것부터 모두 잠기는 경우까지 탐색해야 한다.
비가 내리지 않았을 때 안전 영역의 개수는 1이므로 초기값을 1로 두고, 모든 높이마다 안전 영역의 개수를 bfs로 count한다.

📋코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeSet;

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

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
        // 높이를 저장할 집합 (중복 제거 위해 집합 사용)
        // 자동 정렬될 수 있도록 TreeSet 사용
		TreeSet<Integer> height = new TreeSet<>();
		
		for (int i = 0; i < N; i++) {
			stk = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
            	// map 배열 입력
				map[i][j] = Integer.parseInt(stk.nextToken());
                // 높이 저장
				height.add(map[i][j]);
			}
		}
		
		int ans = 1; // 안전영역 개수 최소값 (비가 내리지 않았을 경우)
        // 모든 높이마다 안전영역 개수 세기
		for (Integer h : height) {
			ans = Math.max(ans, getSafeArea(h));
		}
		
		System.out.println(ans);
	}

	private static int getSafeArea(int h) {
		boolean[][] visited = new boolean[N][N];
		int cnt = 0; // 안전 영역의 개수
		Queue<int[]> queue = new ArrayDeque<int[]>();
        
        // map의 모든 원소를 탐색
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
            	// 비가 내린 높이보다 높으면 안전 영역
                // 안전 영역을 만날 때마다 BFS
				if (map[i][j] > h && !visited[i][j]) {
					queue.offer(new int[] {i, j});
					visited[i][j] = true;
					
					while(!queue.isEmpty()) {
						int[] cur = queue.poll();
						
						for (int d = 0; d < 4; d++) {
							int nx = cur[0] + dx[d];
							int ny = cur[1] + dy[d];
							
							if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
							if (visited[nx][ny] || map[nx][ny] <= h) continue;
							
							visited[nx][ny] = true;
							queue.offer(new int[] {nx, ny});
						}
					}
					cnt++;
				}
				
			}
		}
		
		return cnt;
	}

}

⏱ 시간 복잡도

TreeSet add 시간복잡도 : O(log N).. N번 입력받으니까 결국 NlogN이 걸림.. Arrays.sort와 시간복잡도는 똑같다

2644 촌수 계산

📌문제 링크

https://www.acmicpc.net/problem/2644

💡 문제 풀이

📋코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		int N = Integer.parseInt(br.readLine());
		
        // 촌수를 계산해야 하는 서로 다른 두 사람의 번호 입력
		stk = new StringTokenizer(br.readLine());
		int p1 = Integer.parseInt(stk.nextToken());
		int p2 = Integer.parseInt(stk.nextToken());
		
		int M = Integer.parseInt(br.readLine());
        // 인접행렬
		boolean[][] adj = new boolean[N+1][N+1];
		
		for (int i = 0; i < M; i++) {
			stk = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(stk.nextToken());
			int y = Integer.parseInt(stk.nextToken());
			
			adj[x][y] = true;
			adj[y][x] = true;
		}
		
        // 방문 배열
		boolean[] visited = new boolean[N+1];
        //BFS
		Queue<int[]> queue = new ArrayDeque<int[]>();
        // {현재 사람의 번호, 촌수}
		queue.offer(new int[] {p1, 0});
		visited[p1] = true;
		
		int cnt = -1; // 촌수를 계산할 수 없을 때 -1 출력
		while(!queue.isEmpty()) {
			int[] cur = queue.poll();
			
            // 촌수를 계산해야 하는 사람의 번호를 만나면 break
			if (cur[0] == p2) {
				cnt = cur[1];
				break;
			}
			
			for (int i = 1; i < N+1; i++) {
				if (adj[cur[0]][i] && !visited[i]) {
					visited[i] = true;
					queue.offer(new int[] {i, cur[1]+1});
				}
			}
		}
		
		System.out.println(cnt);
	}
}

⏱ 시간 복잡도