삼성 SDS 대학생 알고리즘 특강 1일차 - DFS&BFS

항상 구현 전에 주석처리하고 시작 할 것.

DFS와 BFS를 구분 짓는 가장 중요한 점 "동시성"

동시에 무언가를 해야한다? BFS!

DFS

방문'한'게 스택에 들어감

 

1.체크인(방문)

2.목적지인가?

3.연결된 곳을 순회

      4.갈 수 있는가?

            5.간다.

6.체크아웃

 

항상 1,6의 뎁스 맞추는 것을 명심해야 한다. 그래야 스택오버플로우 실수를 예방할 수 있음.

 

BFS

방문'할'게 큐에 들어감

 

1.큐에서 꺼내옴

2.목적지인가?

3.연결된 곳을 순회

      4.갈 수 있는가?

            5.체크인

            6.큐에 넣음.

 

 

1062번: 가르침

import java.util.Scanner;

public class Main {
    static int N, K;
    static String[] words;
    static boolean[] visited = new boolean[26];
    static int selectedCount = 0;
    static int max = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        K = sc.nextInt();

        words = new String[N];
        visited['a' - 'a'] = true;
        visited['n' - 'a'] = true;
        visited['t' - 'a'] = true;
        visited['i' - 'a'] = true;
        visited['c' - 'a'] = true;

        if(K == 26){
            System.out.println(N);
        } else if(K<5){
            System.out.println(0);
        } else {
            for (int i = 0; i < N; i++) {
                String str = sc.next();
                //words[i] = str.substring(4,str.length()-4);
                words[i] = str.replaceAll("[antic]", "");
            }

            selectedCount = 5;
            max = countWords();

            for (int i = 0; i < 26; i++) {
                if (visited[i] == false) {
                    dfs(i);
                }
            }
            System.out.println(max);
        }
}

    static void dfs(int index){
//        1.체크인(방문)
          visited[index] = true;
          selectedCount++;
//        2.목적지인가?: selectedCount == K  => 읽을 수 있는 단어 개수 계산
          if(selectedCount == K){
              //계산
              max = Math.max(max,countWords());
          } else {
//        3.연결된 곳을 순회 : index + 1 ~ 25
              for(int i=index+1; i<=25; i++){
//           4.갈 수 있는가? : 방문 여부
                  if(visited[i]==false){
//              5.간다. : dfs()
                      dfs(i);
                  }
              }
          }
//        6.체크아웃
          visited[index] = false;
          selectedCount--;
    }


    static int countWords(){
        int count = 0;
        for(int n=0; n<N; n++){
            boolean isPossible = true;
            String word = words[n];
            for(int i=0; i<word.length(); i++){
                if(visited[word.charAt(i) - 'a']==false) {
                    isPossible = false;
                    break;
                }
            }
            if(isPossible){
                count++;
            }
        }
        return count;
    }
}

 

 

 

1759번: 암호 만들기

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int L, C;
    static char[] data;
    static List<String> result;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        L = sc.nextInt();
        C = sc.nextInt();

        data = new char[C];
        result = new LinkedList<>();

        for (int i = 0; i < C; i++) {
           data[i] = sc.next().charAt(0);
        }

        Arrays.sort(data);

        dfs(0,0,0,-1,"");

        for (int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i));
        }
}

    static void dfs(int length, int ja, int mo, int current, String pwd){
//        1.체크인 - 생략 가능
//        2.목적지인가?: length == L => ja 개수, mo 개수 확인 암호 가능 판별
        if(length == L){
            if(ja>=2 && mo>=1){
                result.add(pwd);
            }
        } else {
//        3.연결된 곳을 순회 : current +1 ~ C
            for(int i= current +1; i<C; i++){
//        4.갈 수 있는가? : 정렬했기 때문에 다 갈 수 있음
//        5.간다 -> ja, mo
                if(data[i]=='a' || data[i]=='e' || data[i]=='i' || data[i]=='o' || data[i]=='u'){
                    dfs(length+1, ja, mo+1, i, pwd+data[i]);
                } else {
                    dfs(length+1, ja+1, mo, i, pwd+data[i]);
                }
            }
        }
//        6.체크아웃 - 생략 가능
    }
}

 

 

 

3055: 탈출

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static class Node {
        int x;
        int y;
        int type;

        public Node(int y, int x, int type){
            this.y = y;
            this.x = x;
            this.type = type;
        }
    }

                          // 좌, 우, 위, 아래
    static final int[] dx = {-1, 1, 0, 0};
    static final int[] dy = {0, 0, -1, 1};

    static int R, C;
    static char[][] map;
    static int[][] dp;
    static Queue<Node> queue;
    static boolean foundAnswer;


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        R = sc.nextInt();
        C = sc.nextInt();

        map = new char[R][C];
        dp = new int[R][C];
        queue = new LinkedList<>();

        Node st = null;
        for (int r = 0; r < R; r++) {
            String str = sc.next();
            for (int c = 0; c < C; c++) {
                map[r][c] = str.charAt(c);
                //물 먼저 넣음. 전제조건에서 다음 턴에 물이 번질 가능성이 있는 위치에는 고슴도치가 이동할 수 없기 때문에
                //물이 먼저 범람하도록 하여 이를 쉽게 해결.
                if (map[r][c] == '*') {
                    queue.add(new Node(r, c, '*'));
                } else if (map[r][c] == 'S') {
                    st = new Node(r, c, 'S');
                }
            }
        }
        queue.add(st);

        while (!queue.isEmpty()) {
//        1.큐에서 꺼내옴(큐에는 이동할 곳이 들어감) -> *, s, ., D
            Node n = queue.poll();
//        2.목적지인가? -> D
            if (n.type == 'D') {
                //답 출력
                System.out.println(dp[n.y][n.x]);
                foundAnswer = true;
                break;
            }
//        3.연결된 곳을 순회 -> 좌우위아래
            for (int i = 0; i < 4; i++) {
                int ty = n.y + dy[i];
                int tx = n.x + dx[i];
//            4.갈 수 있는가? (공통) : 맵 안에 들어오는가
                if (0 <= ty && ty < R && 0 <= tx && tx < C) {
                    if (n.type == 'S' || n.type == '.') {
//                4.갈 수 있는가? (도슴도치) : . or D, 방문하지 않은 곳
                        if ((map[ty][tx] == '.' || map[ty][tx] == 'D') && dp[ty][tx] == 0) {
//                        5.체크인 (고슴도치) : dp[][] = 이동거리
                            dp[ty][tx] = dp[n.y][n.x] + 1;
                            //6. 큐에 넣음
                            queue.add(new Node(ty, tx, map[ty][tx]));
                        }
                    } else if (n.type == '*') {
//                     4.갈 수 있는가? (물) : . (물은 지나가면 알아서 방문체크됨) *물은 S도 방문가능.
                        if (map[ty][tx] == '.' || map[ty][tx] == 'S') {
//                        5.체크인 (물) : map[][] = *
                            map[ty][tx] = '*';
//                        6.큐에 넣음
                            queue.add(new Node(ty, tx, '*'));
                        }
                    }
                }
            }
        }
        if(foundAnswer){
        } else {
            System.out.println("KAKTUS");
        }
    }
}