seaking110 님의 블로그
사전 캠프 7일차 본문
오늘은 DFS/ BFS에 대한 알고리즘을 정리하고 관련 문제를 풀어보려고 한다!
그래프 탐색 방법의 대표적인 2가지로 모든 정점을 한 번씩 방문한다라는 공통점이 있지만 어떻게 방문하냐에 따라 DFS 와 BFS로 나뉜다.
DFS (Depth First Search)
먼저 DFS 는 말 그대로 깊이 우선 탐색으로 stack 혹은 재귀 함수를 사용하여 갈 수 있는 한 최대한 깊이 들어간 후 더 이상 갈 곳이 없다면 이전 정점으로 하나씩 돌아가는 것이다.
기본적인 DFS 알고리즘
dfs (int n){
visited[x] = true;
for(int i=0;i<v;i++){
if(graph[x][i] == 1 && !visited[i])
dfs(i);
}
}
실제 코드에선 조금씩 다를 수 있지만 기본적인 알고리즘으로 방문 여부를 visted 배열에 저장, 해당 노드에 방문 한 적이 없고 연결 된 다른 노드를 찾아서 다시 dfs를 하는 재귀 함수 형식의 알고리즘이다.
DFS 는 언제 사용 할까?
- 모든 노드에 방문 시
- 어떠한 특정 조건을 만족 시켜야 하는 경우
- 경로의 특징을 저장해야 하는 경우 (경로에 같은 숫자가 존재하면 안된다 등등)
DFS 시간 복잡도
그래프의 구현 방식에 따라 달라지는데
인접 행렬의 경우 O(N^2)
인접 리스트의 경우 O(N+E)
N 은 정점의 수, E는 간선의 수
인접 리스트가 인접 행렬에 비해 압도적으로 시간 복잡도가 작다. 앞으로 인접 리스트로도 만들어보자!
BFS (Breadth First Search)
BFS의 기본 원리는 큐를 이용하여 지금 위치에서 갈 수 있는 모든 정점을 모두 큐에 넣는 것이다.
기본적인 BFS 알고리즘
bfs (int n){
q.push(n);
visited[n] = true;
while(!q.empty()){
n = q.pop();
for(int i=0;i<size;i++)
if(!visited[i] && arr[n][i]==1){
q.push(i);
visited[i] = true;
}
}
}
실제 코드에선 조금씩 다를 수 있지만 기본적인 알고리즘으로 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리, 2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입, 방문 처리, 3. 2번의 과정을 계속 반복하여 큐에 남은 노드가 없을 때까지 반복
BFS 는 언제 사용 할까?
- 모든 노드에 방문 시
- 미로 찾기 등 최단 거리를 구해야 할 경우
BFS 시간 복잡도
bfs 역시 그래프의 구현 방식에 따라 달라지는데
인접 행렬의 경우 O(N^2)
인접 리스트의 경우 O(N+E)
N 은 정점의 수, E는 간선의 수
DFS BFS 문제!
1260번 : DFS와 BFS
https://www.acmicpc.net/problem/1260
기본적인 DFS와 DFS를 배울 수 있는 문제
2178번 : 미로탐색
https://www.acmicpc.net/problem/2178
BFS로 최소 거리를 찾는 전형적인 문제이다! DP를 이용해서 이동할때 값을 추가하자!
public class Main {
public static StringBuilder sb = new StringBuilder();
public static boolean visited[][];
public static int [][] arr;
public static int dp[][];
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
arr = new int[m+1][n+1];
dp = new int[m+1][n+1];
visited = new boolean[m+1][n+1];
for(int i=1;i<=n;i++) {
st = new StringTokenizer(bf.readLine(),"1,0",true);
for(int j=1;j<=m;j++) {
arr[j][i] = Integer.parseInt(st.nextToken());
}
}
bfs(n,m,1,1);
}
public static void bfs(int n, int m, int x, int y) {
Queue <String> q = new LinkedList<>();
int x1[] = {-1,0,0,1};
int y1[] = {0,-1,1,0};
visited[x][y] = true;
q.add(x+" "+y);
dp[1][1] = 1;
while(!q.isEmpty()) {
StringTokenizer st2 = new StringTokenizer(q.poll());
x = Integer.parseInt(st2.nextToken());
y = Integer.parseInt(st2.nextToken());
if(x==m && y==n) {
System.out.println(dp[x][y]);
}
for(int i=0;i<4;i++) {
int newX = x + x1[i];
int newY = y + y1[i];
if(newX > 0 && newY > 0 && newX <=m && newY <=n) {
if(arr[newX][newY]==1 && !visited[newX][newY]) {
q.add(newX+" "+newY);
dp[newX][newY] = dp[x][y]+1;
visited[newX][newY] = true;
}
}
}
}
}
}
2606번 : 바이러스
https://www.acmicpc.net/problem/2606
DFS로 count 값 하나만 추가로 넣어서 간단히 풀었습니다
2667번 : 단지 번호 붙이기
https://www.acmicpc.net/problem/2667
bfs를 이용해서 풀었으며 큐에 값을 뺄 때 마다 count를 증가 시켜 단지에 속하는 집의 수를 구했다. 위에 풀었던 미로 탐색 문제와 크게 다르지 않은 문제!
public class Main {
public static StringBuilder sb = new StringBuilder();
public static boolean visited[][];
public static int [][] arr;
public static int dp[][];
public static LinkedList <Integer> list = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bf.readLine());
arr = new int[n+1][n+1];
visited = new boolean[n+1][n+1];
for(int i=1;i<=n;i++) {
StringTokenizer st = new StringTokenizer(bf.readLine(),"0,1",true);
for(int j=1;j<=n;j++) {
int a = Integer.parseInt(st.nextToken());
arr[i][j] = a;
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(arr[i][j] == 1 && !visited[i][j]) {
bfs(n,i,j);
}
}
}
System.out.println(list.size());
Collections.sort(list);
for(int i : list) {
System.out.println(i);
}
}
public static void bfs(int n, int x, int y) {
int x1[] = {-1,0,0,1};
int y1[] = {0,-1,1,0};
visited[x][y] = true;
Queue <String> q = new LinkedList<>();
q.add(x+" "+y);
int count = 0;
while(!q.isEmpty()) {
StringTokenizer st2 = new StringTokenizer(q.poll());
x = Integer.parseInt(st2.nextToken());
y = Integer.parseInt(st2.nextToken());
count++;
for(int i=0;i<4;i++) {
int newX = x + x1[i];
int newY = y + y1[i];
if(newX > 0 && newY > 0 && newX <= n && newY <= n) {
if(arr[newX][newY]==1 && !visited[newX][newY]) {
visited[newX][newY] = true;
q.add(newX+" "+newY);
}
}
}
}
list.add(count);
}
}
7576번 토마토
https://www.acmicpc.net/problem/7576
위에 풀었던 문제들을 전부 혼합해서 푸는 느낌? 많이 까다롭고 맨처음에 문제는 풀었지만 시간 초과가 나서 arr 값에 직접 값을 넣으면서 visited 함수도 빼버리고 간단하게 풀린거 같다! 생각보다 풀고 나면 어렵지 않았던 문제
public class Main {
public static StringBuilder sb = new StringBuilder();
public static int [][] arr;
public static Queue <String> q = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int m = Integer.parseInt(st.nextToken()); // 가로 칸 수
int n = Integer.parseInt(st.nextToken()); // 세로 칸 수
arr = new int[n+1][m+1];
visited = new boolean[n+1][m+1];
int count = 0;
for(int i=1;i<=n;i++) {
st = new StringTokenizer(bf.readLine());
for(int j=1;j<=m;j++) {
int a = Integer.parseInt(st.nextToken());
arr[i][j] = a;
if(a==0) {
count++;
}
}
}
if(count ==0) {
System.out.println(0);
}
else {
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(arr[i][j]==1) {
q.add(i+" "+j);
}
}
}
bfs(n,m);
}
}
public static void bfs(int n, int m) {
int x1[] = {-1,0,0,1};
int y1[] = {0,-1,1,0};
while(!q.isEmpty()) {
StringTokenizer st2 = new StringTokenizer(q.poll());
int y = Integer.parseInt(st2.nextToken());
int x = Integer.parseInt(st2.nextToken());
for(int i=0;i<4;i++) {
int newX = x + x1[i];
int newY = y + y1[i];
if(newX > 0 && newY > 0 && newX <= m && newY <= n) {
if(arr[newY][newX]==0) {
arr[newY][newX] = arr[y][x] + 1;
q.add(newY+" "+newX);
}
}
}
}
int max = -1;
if (checkZero(n,m)) {
System.out.println(-1);
} else {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (max < arr[i][j]) {
max = arr[i][j];
}
}
}
System.out.println(max-1);
}
}
public static boolean checkZero(int n, int m) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (arr[i][j] == 0)
return true;
}
}
return false;
}
}
내일까지 문제를 더 풀어보자! 오늘은 기초적인 문제를 풀었다면 내일은 심화!
