| 1 | 24479 | 알고리즘 수업 - 깊이 우선 탐색 1 |
- N개의 정점, M개의 간선으로 구성된 무방향 그래프(undirected graph)
- 인접 정점은 오름차순으로 방문
- 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static List<ArrayList<Integer>> edges;
private static int cnt;
private static int[] visited;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int R = Integer.parseInt(st.nextToken());
edges = new ArrayList<>();
edges.add(null); // index 0
for(int i = 1; i <= N; i++) { // index 1 ~ N
edges.add(new ArrayList<>());
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(reader.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
edges.get(u).add(v);
edges.get(v).add(u);
}
// 오름차 순 정렬
for(int i = 1; i <= N; i++) {
Collections.sort(edges.get(i));
}
cnt = 1;
visited = new int[N + 1];
dfs(R);
StringBuilder sb = new StringBuilder();
for(int i = 1; i <= N; i++) {
sb.append(visited[i]).append("\n");
}
System.out.print(sb);
}
static void dfs(int start) {
visited[start] = cnt++;
for(int dest : edges.get(start)) { // start와 연결된 정점(dest) 조회
if(visited[dest] == 0) { // 순서 지정 X == 방문 X
dfs(dest);
}
}
}
}
깊이 우선 탐색(DFS, Depth-Frist Search)
루트 노드(혹은 임의의 노드)에서 시작하여 다음 분기(branch)로 넘어가기 전에 해당 분기를 모두 탐색하는 방법
- 자기 자신을 호출하는 순환 알고리즘의 형태를 가짐
- 시작 정점과 인접한 노드 중 방문하지 않은 노드 방문 -> 방문한 노드 기준으로 반복
- 인접한 노드 중 방문하지 않은 노드가 없다면 직전에 방문했던 노드로 backtracking
- 위 과정을 반복하다 시작 정점으로 돌아와 더이상 방문하지 않은 노드가 없다면 탐색 종료
- 노드에 대해 방문했었는지 여부를 검사해야 함 (중복X)
- 모든 노드를 방문하고자 하는 경우 사용
간선을 저장하는 자료구조로 2차원 배열 사용 시 메모리 초과
Collections.sort() 함수로 미리 정렬하지 않고 이중 루프를 사용하여 오름차 순 조회 시 시간 초과
dfs(int start): 정점 start 와 인접한(연결된) 간선을 오름차 순으로 조회하여 방문한 적 없는 정점에 대하여 재귀 호출
| 2 | 24480 | 알고리즘 수업 - 깊이 우선 탐색 2 |
- N개의 정점, M개의 간선으로 구성된 무방향 그래프(undirected graph)
- 인접 정점은 내림차순으로 방문
- 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static List<ArrayList<Integer>> edges;
private static int cnt;
private static int[] visited;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int R = Integer.parseInt(st.nextToken());
edges = new ArrayList<>();
edges.add(null); // index 0
for(int i = 1; i <= N; i++) { // index 1 ~ N
edges.add(new ArrayList<>());
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(reader.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
edges.get(u).add(v);
edges.get(v).add(u);
}
// 내림차 순 정렬
for(int i = 1; i <= N; i++) {
edges.get(i).sort(Comparator.reverseOrder());
}
cnt = 1;
visited = new int[N + 1];
dfs(R);
StringBuilder sb = new StringBuilder();
for(int i = 1; i <= N; i++) {
sb.append(visited[i]).append("\n");
}
System.out.print(sb);
}
static void dfs(int start) {
visited[start] = cnt++;
for(int dest : edges.get(start)) {
if(visited[dest] == 0) { // 순서 지정 X == 방문 X
dfs(dest);
}
}
}
}
1번 문제에서 내림차순 정렬로 변경
| 3 | 24444 | 알고리즘 수업 - 너비 우선 탐색 1 |
- N개의 정점, M개의 간선으로 구성된 무방향 그래프(undirected graph)
- 인접 정점은 오름차순으로 방문
- 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static List<ArrayList<Integer>> edges;
private static int cnt;
private static int[] visited;
private static Queue<Integer> queue;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int R = Integer.parseInt(st.nextToken());
edges = new ArrayList<>();
edges.add(null); // index 0
for(int i = 1; i <= N; i++) { // index 1 ~ N
edges.add(new ArrayList<>());
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(reader.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
edges.get(u).add(v);
edges.get(v).add(u);
}
// 오름차 순 정렬
for(int i = 1; i <= N; i++) {
Collections.sort(edges.get(i));
}
cnt = 1;
visited = new int[N + 1];
queue = new LinkedList<>();
bfs(R);
StringBuilder sb = new StringBuilder();
for(int i = 1; i <= N; i++) {
sb.append(visited[i]).append("\n");
}
System.out.print(sb);
}
static void bfs(int start) {
visited[start] = cnt++;
queue.add(start);
while(!queue.isEmpty()) {
int u = queue.remove();
for(int v : edges.get(u)) {
if(visited[v] == 0) {
visited[v] = cnt++;
queue.add(v);
}
}
}
}
}
너비 우선 탐색(BFS, Breadth-First Search)
루트 노드(혹은 임의의 노드)에서 시작하여 인접한 노드를 먼저 탐색하는 방법
- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
- 두 노드 간 최단 경로 혹은 임의의 경로를 찾을 때 사용
- 노드에 대해 방문했었는지 여부를 검사해야 함 (중복X)
- 방문한 순서대로 저장하고 꺼낼 수 있는 자료구조인 큐(Queue)를 사용하여 구현
- 방문한 노드 -> enqueue
- 현재 노드에서 인접한 노드에 대한 탐색이 끝나고 다음 기준이 될 노드 -> dequeue
Queue 구조로 LinkedList 사용
| 4 | 24445 | 알고리즘 수업 - 너비 우선 탐색 2 |
- N개의 정점, M개의 간선으로 구성된 무방향 그래프(undirected graph)
- 인접 정점은 내림차순으로 방문
- 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static List<ArrayList<Integer>> edges;
private static int cnt;
private static int[] visited;
private static Queue<Integer> queue;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int R = Integer.parseInt(st.nextToken());
edges = new ArrayList<>();
edges.add(null); // index 0
for(int i = 1; i <= N; i++) { // index 1 ~ N
edges.add(new ArrayList<>());
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(reader.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
edges.get(u).add(v);
edges.get(v).add(u);
}
// 내림차 순 정렬
for(int i = 1; i <= N; i++) {
edges.get(i).sort(Comparator.reverseOrder());
}
cnt = 1;
visited = new int[N + 1];
queue = new LinkedList<>();
bfs(R);
StringBuilder sb = new StringBuilder();
for(int i = 1; i <= N; i++) {
sb.append(visited[i]).append("\n");
}
System.out.print(sb);
}
static void bfs(int start) {
visited[start] = cnt++;
queue.add(start);
while(!queue.isEmpty()) {
int u = queue.remove();
for(int v : edges.get(u)) {
if(visited[v] == 0) {
visited[v] = cnt++;
queue.add(v);
}
}
}
}
}
3번 문제에서 내림차순 정렬로 변경
| 5 | 2606 | 바이러스 |
그래프의 한 정점에서부터 도달할 수 있는 정점들을 찾는 문제
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
1번 바이러스가 웜 바이스러스에 감염
바이러스가 전파된 컴퓨터: 2, 5, 3, 6
바이러스가 전파되지 않은 컴퓨터: 4, 7
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static List<ArrayList<Integer>> edges;
private static int cnt = 0;
private static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(reader.readLine());
int E = Integer.parseInt(reader.readLine());
edges = new ArrayList<>();
edges.add(null);
for(int i = 1; i <= N; i++) {
edges.add(new ArrayList<>());
}
for(int i = 0; i < E; i++) {
StringTokenizer st = new StringTokenizer(reader.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
edges.get(u).add(v);
edges.get(v).add(u);
}
visited = new boolean[N + 1];
dfs(1); // 1번에서 시작
System.out.print(cnt);
}
static void dfs(int start) {
visited[start] = true;
for(int v : edges.get(start)) {
if(!visited[v]) {
dfs(v);
cnt++;
}
}
}
}
| 6 | 1260 | DFS와 BFS |
무방향 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램
- 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static List<ArrayList<Integer>> edges;
private static boolean[] visited;
private static Queue<Integer> queue;
private static StringBuilder sb;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(st.nextToken()); // 정점 수
int M = Integer.parseInt(st.nextToken()); // 간선 수
int V = Integer.parseInt(st.nextToken()); // 시작 정점
edges = new ArrayList<>();
edges.add(null);
for(int i = 1; i <= N; i++) {
edges.add(new ArrayList<>());
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(reader.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
edges.get(u).add(v);
edges.get(v).add(u);
}
// 오름차순 정렬
for(int i = 1; i < edges.size(); i++) {
Collections.sort(edges.get(i));
}
sb = new StringBuilder();
visited = new boolean[N + 1];
dfs(V);
sb.append("\n");
visited = new boolean[N + 1];
queue = new LinkedList<>();
bfs(V);
System.out.print(sb);
}
static void dfs(int start) {
visited[start] = true;
sb.append(start).append(" ");
for(int v : edges.get(start)) {
if(!visited[v]) {
dfs(v);
}
}
}
static void bfs(int start) {
visited[start] = true;
queue.add(start);
sb.append(start).append(" ");
while (!queue.isEmpty()) {
int u = queue.remove();
for(int v : edges.get(u)) {
if(!visited[v]) {
visited[v] = true;
sb.append(v).append(" ");
queue.add(v);
}
}
}
}
}
| 7 | 2667 | 단지번호붙이기 |
2차원 배열을 그래프로 표현해 BFS나 DFS로 순회하는 문제
<그림 1> 정사각형 모양의 지도 (1: 집이 있는 곳, 0: 집이 없는 곳)
이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다.
여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다.
대각선상에 집이 있는 경우는 연결된 것이 아니다.
<그림 2> <그림 1>을 단지별로 번호를 붙인 것
지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N;
private static boolean[][] visited;
private static boolean[][] map;
private static int cnt;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(reader.readLine());
map = new boolean[N][N];
for(int i = 0; i < N; i++) {
String line = reader.readLine();
for(int j = 0; j < line.length(); j++) {
map[i][j] = line.charAt(j) != '0';
}
}
visited = new boolean[N][N];
cnt = 0;
List<Integer> results = new ArrayList<>();
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
// 집이 존재하고(map == true) 방문한 적 없으면(visited == false) 탐색
if(map[i][j] && !visited[i][j]) {
dfs(i, j);
results.add(cnt);
cnt = 0; // 단지 탐색에 사용했던 정적 변수 초기화
}
}
}
// 오름차순 정렬
Collections.sort(results);
System.out.println(results.size()); // 단지 수
for(int n : results) {
System.out.println(n); // 각 단지의 가구 수
}
}
static void dfs(int x, int y) {
visited[x][y] = true;
cnt++;
// (x,y)와 인접한 좌표: (x-1, y), (x, y-1), (x+1, y), (x, y+1)
if(x > 0 && map[x-1][y] && !visited[x-1][y]) {
dfs(x-1, y);
}
if(y > 0 && map[x][y-1] && !visited[x][y-1] ) {
dfs(x, y-1);
}
if(x+1 < N && map[x+1][y] && !visited[x+1][y]) {
dfs(x+1, y);
}
if(y+1 < N && map[x][y+1] && !visited[x][y+1]) {
dfs(x, y+1);
}
}
}
| 8 | 1012 | 유기농 배추 |
땅의 모습이 아니라 배추의 위치(좌표)가 주어지는 문제
- 배추흰지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다.
- 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.
- 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.
- 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static boolean[][] visited;
private static boolean[][] map;
private static int M;
private static int N;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(reader.readLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < T; i++) {
StringTokenizer st = new StringTokenizer(reader.readLine());
M = Integer.parseInt(st.nextToken()); // 가로 길이
N = Integer.parseInt(st.nextToken()); // 세로 길이
int K = Integer.parseInt(st.nextToken()); // 배추가 심어진 위치의 개수
map = new boolean[M][N];
visited = new boolean[M][N];
for(int j = 0; j < K; j++) {
st = new StringTokenizer(reader.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
map[x][y] = true;
}
int cnt = 0; // 지렁이 수
for(int x = 0; x < M; x++) {
for(int y = 0; y < N; y++) {
// 배추가 존재하고(map == true) 방문한 적 없으면(visited == false) 탐색
if(map[x][y] && !visited[x][y]) {
dfs(x, y);
cnt++;
}
}
}
sb.append(cnt).append("\n");
}
System.out.print(sb);
}
static void dfs(int x, int y) {
visited[x][y] = true;
if(x > 0 && map[x-1][y] && !visited[x-1][y]) {
dfs(x-1, y);
}
if(y > 0 && map[x][y-1] && !visited[x][y-1]) {
dfs(x, y-1);
}
if(x+1 < M && map[x+1][y] && !visited[x+1][y]) {
dfs(x+1, y);
}
if(y+1 < N && map[x][y+1] && !visited[x][y+1]) {
dfs(x, y+1);
}
}
}
| 9 | 2178 | 미로 탐색 |
BFS의 특징은 각 정점을 최단경로로 방문한다는 것입니다. 이 점을 활용해 최단거리를 구해 봅시다.
- N개의 줄, M개의 정수(0, 1)로 이루어진 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.
- 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static final int[] dx = { -1, 1, 0, 0};
private static final int[] dy = { 0, 0, -1, 1};
private static boolean[][] visited;
private static int[][] map;
private static Queue<Integer> qX;
private static Queue<Integer> qY;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] str = reader.readLine().split(" ");
int N = Integer.parseInt(str[0]);
int M = Integer.parseInt(str[1]);
map = new int[N][M];
visited = new boolean[N][M];
for(int i = 0; i < N; i++) {
String line = reader.readLine();
for(int j = 0; j < M; j++) {
map[i][j] = line.charAt(j) - '0';
}
}
qX = new LinkedList<>();
qY = new LinkedList<>();
// 출발 위치 (0, 0)
bfs(0, 0);
// 도착 위치에 누적된 분기 레벨 반환
System.out.println(map[N-1][M-1]);
}
static void bfs(int startX, int startY) {
qX.add(startX);
qY.add(startY);
visited[startX][startY] = true;
while(!qX.isEmpty() && !qY.isEmpty()) {
int x = qX.remove();
int y = qY.remove();
// 현재 위치 (x,y)에서 인접한 칸 탐색
for(int i = 0; i < dx.length; i++) {
int nextX = x + dx[i];
int nextY = y + dy[i];
if(nextX < 0 || nextY < 0 || nextX >= map.length || nextY >= map[0].length) {
continue;
}
if(map[nextX][nextY] == 0 || visited[nextX][nextY]) {
continue;
}
qX.add(nextX);
qY.add(nextY);
visited[nextX][nextY] = true;
map[nextX][nextY] += map[x][y]; // 다음 위치 값(1)에 현재 위치 값 누적
// map[nextX][nextY] = map[x][y] + 1;
}
}
}
}
- 이동 가능한 범위: 상(x+1,y), 하(x-1, y), 좌(x, y-1), 우(x, y+1)
- 이동 가능 조건: map == 1 && !visited
- 현재 위치에서 이동 가능한 위치의 값 = [ 현재 위치의 값 + 1 ]
- 도착점에 누적된 값이 최단거리가 됨
'CT' 카테고리의 다른 글
| [BOJ] 31단계. 최단 경로 (0) | 2024.05.20 |
|---|---|
| [BOJ] 30단계. 그래프와 순회 2 (0) | 2024.05.10 |
| [BOJ] 29단계 스택2 (0) | 2023.07.21 |
| [BOJ] 28단계 동적 계획법 2 (0) | 2023.06.16 |
| [BOJ] 27단계 우선순위 큐 (0) | 2023.06.14 |
