[99클럽 코테 스터디] 5일차

오늘의 학습 키워드

• BFS

문제 - 비기너

모스 부호

풀이

import java.util.*;

class Main {
  public static Map<String, String> map = new HashMap<>();

  public static void main(String[] args) {
    map.put(".-", "A");
    map.put("-...", "B");
    map.put("-.-.", "C");
    map.put("-..", "D");
    map.put(".", "E");
    map.put("..-.", "F");
    map.put("--.", "G");
    map.put("....", "H");
    map.put("..", "I");
    map.put(".---", "J");
    map.put("-.-", "K");
    map.put(".-..", "L");
    map.put("--", "M");
    map.put("-.", "N");
    map.put("---", "O");
    map.put(".--.", "P");
    map.put("--.-", "Q");
    map.put(".-.", "R");
    map.put("...", "S");
    map.put("-", "T");
    map.put("..-", "U");
    map.put("...-", "V");
    map.put(".--", "W");
    map.put("-..-", "X");
    map.put("-.--", "Y");
    map.put("--..", "Z");
    map.put(".----", "1");
    map.put("..---", "2");
    map.put("...--", "3");
    map.put("....-", "4");
    map.put(".....", "5");
    map.put("-....", "6");
    map.put("--...", "7");
    map.put("---..", "8");
    map.put("----.", "9");
    map.put("-----", "0");
    map.put("--..--", ",");
    map.put(".-.-.-", ".");
    map.put("..--..", "?");
    map.put("---...", ":");
    map.put("-....-", "-");
    map.put(".--.-.", "@");

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    sc.nextLine();

    String mos = sc.nextLine();
    String[] mosArr = mos.split(" ");
    String[] answer = new String[mosArr.length];

    for(int i = 0; i < mosArr.length; i++) {
        answer[i] = map.get(mosArr[i]);
    }

    for(String ans : answer) {
      System.out.print(ans);
    }

  }
}

문제 - 미들러

알고리즘 수업 - 너비 우선 탐색 1

풀이

import java.util.*;

class Main {
  public static int n;
  public static int m;
  public static int r;
  public static int rank;

  public static boolean[] visited;
  public static ArrayList<ArrayList<Integer>> graph;
  public static int[] answer;

  public static void bfs(int start) {
    Queue<Integer> q = new LinkedList<>();

    visited[start] = true;
    q.offer(start);

    while(!q.isEmpty()) {
      int x = q.poll();
      answer[x] = rank++;

      for(int i = 0; i < graph.get(x).size(); i++) {
        int y = graph.get(x).get(i);

        if(!visited[y]) {
          visited[y] = true;
          q.offer(y);
        }
      }
    }
  }

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

    n = sc.nextInt();
    m = sc.nextInt();
    r = sc.nextInt();
    rank = 1;

    visited = new boolean[n + 1];
    graph = new ArrayList<>();
    answer = new int[n + 1];

    for(int i = 0; i <= n; i++) {
      graph.add(new ArrayList<Integer>());
    }

    for(int i = 0; i < m; i++) {
      int x = sc.nextInt();
      int y = sc.nextInt();

      graph.get(x).add(y);
      graph.get(y).add(x);
    }

    for(int i = 0; i < graph.size(); i++) {
      Collections.sort(graph.get(i));
    }

    bfs(r);

    for(int i = 1; i <= n; i++) {
      System.out.println(answer[i]);
    }
  }
}

• BFS를 공부하고 기록했습니다.