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

오늘의 학습 키워드

• DFS

문제 - 비기너

숫자 문자열과 영단어

풀이

class Solution {
    public int solution(String s) {
        String[] words = new String[] {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};

        for(int i = 0; i < words.length; i++) {
            if(s.contains(words[i])) {
                s = s.replace(words[i], String.valueOf(i));
            }
        }

        return Integer.parseInt(s);
    }
}

문제 - 미들러

알고리즘 수업 - 깊이 우선 탐색 1

풀이

import java.util.*;

class Main {
  public static int[] answer;
  public static int n;  // 정점의 수
  public static int m;  // 간선의 수
  public static int r;  // 시작 정점

  public static boolean[] visited;
  public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
  public static int rank;

  public static void dfs(int x) {
    visited[x] = true;
    answer[x] = rank;

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

      if(!visited[y]) {
        rank++;
        dfs(y);
      }
    }
  }

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

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

    rank = 1;
    answer = new int[n + 1];
    visited = new boolean[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));
    }

    dfs(r);

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

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