이것이코딩테스트다 2021 : 3.DFS & BFS

ParkIsComing·2024년 1월 15일
코테공부

코딩테스트

목록 보기
3/5
post-thumbnail

DFS

  • 스택(또는 재귀함수) 이용
  • 모든 노드를 방문하고자 하는 경우 선택
  • DFS가 너비 BFS보다 좀 더 간단함
  • 검색 속도 자체는 BFS에 비해서 느림

[동작 과정]

  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
  2. 스택 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  3. 더이상 2번의 과정을 수행할 수 없을 때까지 반복
import java.util.*;

public class Main {
    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>;
    
    public static void dfs(int x) {
        visited[x] = true;
        System.out.print(x+ " ");
         // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for (int i = 0; i < graph.get(x).size(); i++) {
            int y = grpah.get(x).get(i);
            if (!visited[y]) {
                dfs(y);
            }
        }
    }
    
    public static void main(String args[]) {
     
    }
}

BFS

  • 큐 이용
  • 주로 두 노드 사이의 최단 경로를 찾고 싶을 때

[동작 과정]

  1. 탐색 시작 노드를 큐에 삽입하고 방문처리
  2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
  3. 더이상 2번의 과정을 수행할 수 없을 때까지 반복
import java.util.*;

public class Main {
    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>;
    
    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.print(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;
               }
           }
       }
    }
    
    public static void main(String args[]) {
        // 생략
    }
}

문제) 음료수 얼려 먹기

문제


접근 방법

DFS 활용

  1. 특정 지점의 상하좌우 위치중 값이 0이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문
  2. 방문한 지점에서 1의 과정을 반복하면 연결된 모든 지점을 방문할 수 있음
  3. 모든 노드에 대하여 1~2번 과정을 반복하여, 방문하지 않은 지점의 수를 카운트

BFS 활용

  1. 맵 전체를 돌면서 bfs를 돌림
    1-1. 큐에 시작점 삽입. 해당 지점이 0일 경우 방문 처리 & 큐에 삽입& 상하좌우에 0인 지점이 있으면 큐에 해당 위치 삽입. 앞의 과정을 큐가 빌 때까지 반복하고 큐가 비면 true 반환
    1-2. 특정 지점이 1일 경우 false 반환
  2. 1번 과정을 n*m번만큼 반복. 매 과정에서 true가 반환되면 결과값을 하나씩 증가시켜줌.

해결

자바 (DFS)

import java.util.*;

public class Main {
    
    public static int n, m;
    public static int[][] graph = new int[1000][1000];
    
    public static boolean dfs(int x, int y) {
        // 좌표값이 범위밖이면 즉시 종료
       if (x <= -1 || x >= n || y <= -1 || y >= m) {
           return false;
       }
       // 현재 노드를 아직 방문하지 않았다면
       if (graph[x][y] == 0) {
           graph[x][y] = 1;
           dfs(x-1, y); //상
           dfs(x, y-1); // 좌
           dfs(x+1, y); // 하
           dfs(x, y+1); // 우
           return true;
       }
       return false; //좌표값이 범위내이지만 1인 좌표(방문했거나 구멍이 뚫리지 않은 곳)
    }
    
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
    
        n = sc.nextInt();
        m = sc.nextInt();
        sc.nextLine(); // 버퍼 지우기
        
        for(int i = 0; i < n; i++) {
            String str = sc.nextLine();
            for(int j = 0; j < m; j++) {
                graph[i][j] = str.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 += 1;
                }
            }
        }
        
        System.out.println(result);
    }
}

자바(BFS)

import java.util.*;
import java.awt.Point;

public class Main {
    public static int n,m;
    public static int[][] graph = new int[1000][1000];
    public static int[][] directions = {{0,1}, {0,-1}, {1,0},{-1,0}};
    
    public static boolean bfs (int x, int y) {
        if (graph[x][y] == 0) {
            Queue<Point> q = new LinkedList<Point>();
            
            q.offer(new Point(x,y));
            graph[x][y] = 1;
            
            // queue가 빌 때까지 반복후 없어지면 true 리턴
            while (!q.isEmpty()) {
                Point p = q.poll();
                int row = p.x;
                int col = p.y;
                
                for (int[] direction : directions) {
                    int dx = direction[0];
                    int dy = direction[1];
                    
                    if (row+dy >= 0 && row+dy <= n-1 && col+dx >= 0 && col+dx <= m-1 ) {
                        if (graph[row+dy][col+dx] == 0) {
                            q.offer(new Point(row+dy,col+dx));
                            graph[row+dy][col+dx] = 1;
                        }

                    } 
                }
                
            }
            return true;
        }
        return false;
    }
    public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);
      
      n = sc.nextInt();
      m = sc.nextInt();
      sc.nextLine();
    
      for(int i = 0; i < n; i++) {
        String str = sc.nextLine();
        for(int j = 0; j < m; j++) {
            graph[i][j] = str.charAt(j) - '0';
        }
      }
      
      int result = 0;
      for (int i=0; i<n; i++) {
          for(int j=0; j<m; j++) {
              if(bfs(i,j)) {
                  result += 1;
              }
          }
      }
      
      System.out.println(result);
    }
}

문제) 미로 탈출

문제


접근 방법

  • BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색
  • 상하좌우로 연결된 모든 노드로의 거리가 1로 동일
  • 따라서 (1,1) 지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록
  • 예시로 다음과 같이 3*3 크기의 미로가 있다고 가정

해결

자바

import java.util.*;
import java.awt.Point;

public class Main {
    public static int n,m;
    public static int[][] graph = new int[200][200];
    public static int[][] directions = {{-1,0}, {1,0}, {0,-1},{0,1}};
    
    public static int bfs (int x, int y) {
        Queue<Point> q = new LinkedList<Point>();
        q.offer(new Point(x,y));

        while (!q.isEmpty()) {
            Point p = q.poll();

            for (int[] direction : directions) {
                int nx = p.x + direction[0];
                int ny = p.y + direction[1];
                
                // 영역 밖
                if (nx < 0 || nx >= n || ny < 0 || ny >= m ) {
                    continue;
                } 
                
                // 괴물이 있는 곳
                if (graph[nx][ny] == 0) {
                    continue;
                }
        
                // 상하좌우 중 처음 방문하는 곳만 최단거리 업데이트
                if (graph[nx][ny] == 1) {
                    graph[nx][ny] = graph[p.x][p.y] + 1;
                    q.offer(new Point(nx, ny));
                }
            }
            
        }
        return graph[n-1][m-1];

    
    }
    public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);
      
      n = sc.nextInt();
      m = sc.nextInt();
      sc.nextLine();
    
      for(int i = 0; i < n; i++) {
        String str = sc.nextLine();
        for(int j = 0; j < m; j++) {
            graph[i][j] = str.charAt(j) - '0';
        }
      }
    
      
      System.out.println(bfs(0,0));
    }
}

문제) 특정 거리의 도시 찾기

문제

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

접근 방식

모든 도로의 거리는 1이다
-> 가중치그래프x
-> 모든 간선의 비용이 1
-> bfs를 이용해 최단거리를 찾는다.

해결

자바

import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static int n, m;
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    public static int[] d = new int[300001];
    
    public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        
        q.offer(start);
        d[start] = 0;
        
        while(!q.isEmpty()) {
            int x = q.poll();
            for (int i : graph.get(x)) {
                if (d[i] == -1) {
                    d[i] = d[x] + 1;
                    q.offer(i);
                }
            }
        }
        
        boolean check = false;
        for (int i = 1; i <= n; i++) {
            if (d[i] == k) {
                System.out.println(i);
                check = true;
            }
        }

        if (!check) {
            System.out.println(-1);
        }
    }
    
    public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      
      n = Integer.parseInt(st.nextToken());
      m = Integer.parseInt(st.nextToken());
      k = Integer.parseInt(st.nextToken());
      x = Integer.parseInt(st.nextToken());
      
      // 그래프 초기화
      for (int i=0; i<=n; i++) {
          graph.add(new ArrayList<Integer>());
          d[i] = -1; // - 1이면 미방문
      }
      
      // 도로 정보 입력
      for (int i=0; i<m; i++) {
          st = new StringTokenizer(br.readLine());
          int a = Integer.parseInt(st.nextToken());
          int b = Integer.parseInt(st.nextToken());
          graph.get(a).add(b);
      }
      
      bfs(x);
    }
}
profile
ParkIsComing
이전 포스트

이것이코딩테스트다 2021 : 4.정렬

다음 포스트

이것이코딩테스트다 2021 : 5.이진탐색

0개의 댓글