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)
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)
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)
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});
}
}
}
}
}
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와 시간복잡도는 똑같다
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);
}
}