[BOJ] 15886. 내 선물을 받아줘 2(DFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

처음에는 

연결된 길을 찾아 길번호를 지정해주는 느낌으로 해결했다.

첫 번째 좌표를 시작으로 연결된 길을 찾는데,

이미 길번호가 정해진 곳은 pass 해준다.

//

예제로 동작을 살펴보자.

E E W W E W

[방향]

E : ->

W : <-

===> 첫 번째 길 찾기

E E W W E W

1 1 1

===> 두 번째 길 찾기

E E W W E W

1 1 1 2

2번 길은 1번 길과 연결되어 결국 1번으로 길에 포함이 된다.

1 1 1 1

===> 세 번째 길 찾기

E E W W E W

1 1 1 1 3 3

마지막으로,

길 개수를 세어주면 된다.

+++

그런데 생각해보니까 'EW'로 된 지점에서 무한루프가 생성되는데

어느 좌표에서 출발해도 결국 이 무한루프의 늪에 빠지게 된다.

결국 무한루프가 생성되는 좌표가 구사과가 선물을 가져갈 수 있는 지점이 되고,

'EW'로 된 지점의 개수를 count하면 된다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays;   public class BOJ15886 {       static int N, num[];     static char map[];          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                  N = Integer.parseInt(br.readLine());         map = new char[N];         num = new int[N];         map = br.readLine().toCharArray();                  System.out.println(process());     }       private static int process() {                  int id = 0;         for (int i = 0; i < N; i++) {             // 이미 길번호가 정해졌다면 pass             if(num[i] != 0) continue;             go(i, ++id);         }                  int res = 0;         int prev = num[0];         for (int i = 1; i < N; i++) {             if(prev != num[i]) res++;             prev = num[i];         }                  return res + 1;     }       private static int go(int idx, int id) {         // 이미 길번호가 정해진 길이면         if(num[idx] != 0) return num[idx];                  num[idx] = id;                  int tmp = id;         if(map[idx] == 'E') {             tmp = go(idx + 1, id);         } else {             tmp = go(idx - 1, id);         }                  // 이미 있는 길에 포함된다면         return num[idx] = tmp;     }   }   Colored by Color Scripter

cs

#. Code_v2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class BOJ15886_v2 {
 
    static int N;
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        String map = br.readLine();
        
        int res = 0;
        for (int i = 0; i < N - 1; i++) {
            if(map.charAt(i) == 'E' && map.charAt(i + 1) == 'W') res++; 
        }
        
        System.out.println(res);
    }
 
}