[자바] 백준 16956 - 늑대와 양 (java)

 문제 : boj16956

---

 

필요 알고리즘 개념

• 애드 혹, 구성적
  
  • 어떨 때 늑대와 양을 분리시킬 수 있는지와 없는지 생각해보면 생각보다 간단하게 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  우선 어떨 때 무슨짓을 해도 늑대가 양이 있는 칸으로 갈 수 있을까? S와 W가 인접해있는 경우이다. 즉

1. SW

2. WS

3. 

   S

   W

4.

   W

   S

 

  위와 같은 경우엔 무슨짓을 해도 늑대가 양한테 갈 수 있다. 따라서 위와 같은 경우가 하나라도 존재한다면 0을 출력해주고 종료하면 된다.

 

  그럼 울타리는 어떻게 채우면 될까? 문제에 적혀있는 '이 문제는 설치해야 하는 울타리의 최소 개수를 구하는 문제가 아니다.'가 핵심이다. 뭔말이냐면, 그냥 위의 4가지 경우만 없다면, '.'을 전부 'D'로 채우면 끝이다 ㅋㅋ 즉 replaceAll로 '.'을 'D'로 바꿔주면 된다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        StringBuilder answer = new StringBuilder();
        answer.append('1').append('\n');
        ArrayList<Integer> wolf = new ArrayList<>();
        ArrayList<Integer> sheep = new ArrayList<>();
        for (int i = 0; i < r; i++) {
            String cur = br.readLine();
            if (cur.indexOf("SW") != -1 || cur.indexOf("WS") != -1) {
                System.out.println(0);
                return;
            }
            for (int w : wolf) {
                if (cur.charAt(w) == 'S') {
                    System.out.println(0);
                    return;
                }
            }
            for (int s : sheep) {
                if (cur.charAt(s) == 'W') {
                    System.out.println(0);
                    return;
                }
            }
            wolf = new ArrayList<>();
            for (int j = 0; j < c; j++)
                if (cur.charAt(j) == 'W')
                    wolf.add(j);
            sheep = new ArrayList<>();
            for (int j = 0; j < c; j++)
                if (cur.charAt(j) == 'S')
                    sheep.add(j);
            answer.append(cur.replaceAll("\\.", "D")).append('\n');
        }
        System.out.println(answer);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}