[백준] 15886번 : 내 선물을 받아줘 2 - 자바[Java]

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

15886번: 내 선물을 받아줘 2

풀이

처음 문제를 봤을 때는 BFS 알고리즘을 생각했다. 같은 위치를 다시 방문하면 안되기 때문에 boolean[] visited 방문 배열을 사용해야겠다고 생각했다.

하지만 단순한 방문배열이 아닌, 현재 탐색 단계와 이전 탐색 단계를 구분하는 방문 배열이 필요하다.

 

ex) EEW W EW

- 인덱스가 3인 W부터 시작해서 탐색할 때 왼쪽의 EEW와 합쳐진다. 따라서 카운트하지 않는다.

- 인덱스가 4인 E부터 시작해서 탐색할 때, E -> W -> E로 현재 단계에서 탐색한 E를 만나기 때문에, 카운트한다.

 

즉 현재 탐색 단계와 이전 탐색 단계를 구분하는 배열이 필요하였고, int형 배열 step을 생성했다.

 

코드

import java.io.*;

public class Main {

    static int[] step; // 해당 위치를 몇번째 탐색단계에 방문했는지 저장

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String str = br.readLine();

        step = new int[n];
        int cnt = 0; // 정답
        int stepNum = 1; // 현재 탐색단계 번호

        for (int i = 0; i < n; i++) {
            if (step[i] == 0) { // 한번도 방문하지 않았으면 함수 실행
                if (bfs(n, str, i, stepNum)) {
                    cnt++;
                }

                stepNum++;
            }
        }

        System.out.println(cnt);
    }

    static boolean bfs(int n, String str, int startIdx, int stepNum) {
        int idx = startIdx;
        step[idx] = stepNum;

        while (true) {
            if (str.charAt(idx) == 'E') {
                idx++;
            } else {
                idx--;
            }

            if (step[idx] == 0) {
                step[idx] = stepNum;
            }
            else return step[idx] == stepNum;
        }
    }
}

 

다른 풀이 1

https://www.acmicpc.net/source/75407824

탐색할 때 왼쪽에서부터 시작하여 오른쪽으로 이동하면서 탐색하기 때문에, 이러한 성질을 이용한다.

    int n = Integer.parseInt(br.readLine());
    char[] arr = br.readLine().toCharArray();
    boolean[] used = new boolean[n];
    int answer = 0;
    Queue<Character> q = new LinkedList<>();
    //E E W W E W
    //o o o   o
    // E E E E W
    // o o o o

    for(int i = 0 ; i < n ; i ++){
      if(arr[i]=='E'){
        used[i] = true;
      }else if(arr[i]=='W'){
        if(i-1>=0){
          used[i-1] = true;
        }
      }
    }
    
    for(boolean a : used){
      if(!a) answer++;
    }
    
    bw.write(answer+"");

 

 

다른 풀이 2

https://data-make.tistory.com/580

'EW'로 된 지점에서 무한루프가 생성되기 때문에, 결국 무한루프가 생성되는 좌표가 구사과가 선물을 가져갈 수 있는 지점이 되고, 'EW'로 된 지점의 개수를 count하면 된다.

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);
    }