백준, 늑대와 양(16956, java)

문제 설명

일단 들어가기 전에 먼저 알아야 할 것은 해당 문제에는 스페셜 저지가 있다는 의미이다. 꼭 예제에 있는 출력만이 답이 아니라는 의미로 조건만 맞으면 다른 출력도 답으로 인정이 된다.

 

또한 울타리의 최소 갯수를 구하는 문제가 아니다. 위의 두 조건을 모르고 풀었을 때는 왜 이 문제가 실버 3밖에 되지 않는지 이해할 수 없었지만, 조건들을 알고 나니 굉장히... 사실 어느 기교도 없이 풀 수 있는 문제였다.

 

문제 풀이

그냥 늑대의 사방에 울타리를 씌우면 끝이 난다. 그냥... 이게 문제 풀이의 전부이다.

 

1. 지도 정보를 받을 때 늑대의 위치를 큐에 넣는다.

2. BFS에서 하듯이 큐에서 값을 하나씩 꺼내서 해당 위치의 사방에 접근한다.

3. 만일 접근한 곳에 .이 있으면 D를 표시해 울타리를 세운다.

4. S가 있다면 이 의미는 울타리를 세우지 못해 양이 공격받는 것이니 false를 반환한다.

 

코드

java

import java.util.*;
import java.io.*;

class Pair {
    int row;
    int col;

    Pair(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

public class Main {

    public static int R, C;
    public static char[][] map;
    public static int[] dR = {-1, 0, 1, 0};
    public static int[] dC = {0, 1, 0, -1};
    public static Queue<Pair> queue;

    public static boolean bfs() {
        while (!queue.isEmpty()) {
            Pair current = queue.poll();
            int cR = current.row;
            int cC = current.col;

            for (int i=0; i<4; i++) {
                int nR = cR + dR[i];
                int nC = cC + dC[i];

                if (nR >= 0 && nR < R && nC >= 0 && nC < C) {
                    if (map[nR][nC] == '.' ) {
                        map[nR][nC] = 'D';
                    }
                    if (map[nR][nC] == 'S') {
                        return false;
                    }
                }
            }
        }

        return true;
    }

    public static void display() {
        for (int i=0; i<R; i++) {
            for (int j=0; j<C; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        queue = new LinkedList<>();
        for (int i=0; i<R; i++) {
            String s = br.readLine();
            for (int j=0; j<C; j++) {
                map[i][j] = s.charAt(j);
                if (map[i][j] == 'W') {
                    queue.add(new Pair(i, j));
                }
            }
        }

        if (bfs()) {
            System.out.println("1");
            display();
        } else {
            System.out.println("0");
        }

    }

}