[백준/JAVA] 16956번: 늑대와 양

📖 문제

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

 

 

💡  풀이 방식

• BFS

 

늑대 주변만 울타리로 감싸면 된다.

 

1. 늑대의 위치를 큐에 저장한다.

2. 각 늑대의 위치들을 돌며 인접한 칸을 방문하며 이동할 다음 칸이 ① 빈 칸(.)인 경우에는 울타리를 설치하고, ② 양(S)이라면 함수를 종료한다.

3. 만약 늑대가 양이 있는 칸으로 이동할 수 있다면 0을 출력하고 종료한다. / 이동할 수 없다면 1을 출력하고, 격자를 출력하낟.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
 
    static int R,C;
    static char[][] map;
    static Queue<int[]> q = new ArrayDeque<>();
    static boolean canGo = false;   // 늑대가 양이 있는 칸으로 갈 수 있는지 판단하는 변수
 
    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];
 
        for(int i = 0 ; i < R ; i++) {
            char[] ch = br.readLine().toCharArray();
            for(int j = 0 ; j < C ; j++) {
                map[i][j] = ch[j];
 
                // 늑대 위치 저장
                if(map[i][j] == 'W') q.add(new int[] {i,j});
            }
        }
 
        bfs();
 
        // 늑대가 양이 있는 칸으로 갈 수 있다면, 0 출력하고 종료
        if(canGo) {
            System.out.println(0);
            return;
        }
 
        System.out.println(1);
        for(int i = 0 ; i < R ; i++) {
            for(int j = 0 ; j < C ; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }
 
    private static void bfs() {
        while(!q.isEmpty()) {
            int[] now = q.poll();
 
            for(int d = 0 ; d < 4 ; d++) {  // 늑대가 인접한 칸으로 이동
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
 
                if(nx >= 0 && nx < R && ny >= 0 && ny < C) {
                    if(map[nx][ny] == '.') {    // 빈 칸이라면, 울타리 설치
                        map[nx][ny] = 'D';
                    }
                    if(map[nx][ny] == 'S') {    // 양이라면, 종료
                        canGo = true;
                        return;
                    }
                }
            }
        }
    }
}
 

 

---

💦 어려웠던 점

- 울타리의 위치를 의미 있는 곳에만 설치(=최솟값으로 설치)해야 하는 게 아닐까?해서 구현 방법을 망설였다.

 

 

🧐 새로 알게 된 내용

- 울타리의 위치는 큰 의미가 없다. 그냥 늑대가 양에게 접근하지 못하도록 주변의 빈 칸에 울타리를 설치해주는 것이 포인트,,

- 아 스페셜 저지 문제는 예제 출력과 답이 달라도 상관 없다고 ㄴㅇㄱ

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준] 16956번 늑대와 양 - Java, 자바