[백준] 16956 늑대와 양(Java)

문제링크

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

문제분석

• 목장의 각칸은 3가지 경우 중 하나이다 - 비어있다, 양, 늑대
• 늑대 : 상하좌우로 이동 가능
• 늑대가 양이 있는 칸으로 이동할 수 없도록 울타리를 설치하라!

입력

• 목장의 크기 R, C
• 1<= R,C <=500
• 목장의 상태 : '.'-빈칸, 'S'-양, 'W'-늑대

출력

• 늑대가 양으로 못가게 할 수 있다 => 1 과 울타리를 설치한 목장의 상태
• 늑대를 막는것이 불가능하다 => 0을 출력

풀이

두가지로 나누어 생각한다

• 늑대가 양으로 가는 것을 막을 수 있나?
  • 양의 상하좌우에 늑대가 있는지 검사 : 인접한 상하좌우에 늑대가 있다면, 울타리로 늑대를 막을 수 없다.
• 막을 수 있다면 늑대의 상하좌우에 울타리를 친다
  • 늑대의 상하좌우에 울타리를 친다면 늑대는 이동할 수 없기 때문이다.
  • 주의! 상하좌우에 늑대가 있다면 해당 위치는 울타리를 칠 수 없다.

전체 코드

import java.util.*;

class Point{
    int r, c;

    public Point(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

public class Main {
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0,1, 0, -1};
    static char[][] map;
    static int r, c;
    
    public static void main(String[] args) {
        // 양과 늑대의 위치를 저장할 리스트
        ArrayList<Point> sheepList = new ArrayList<>();
        ArrayList<Point> wolfList = new ArrayList<>();
        Scanner scanner = new Scanner(System.in);
        r = scanner.nextInt();
        c = scanner.nextInt();
        map = new char[r][c];

        //map에 입력을 받으며
        //양이나 늑대가 나오면 위치 저장
        for(int i=0; i<r; i++){
            String line = scanner.next();
            for(int j=0; j<c; j++){
                map[i][j]=line.charAt(j);
                if(map[i][j]=='S'){
                    sheepList.add(new Point(i, j));
                }else if(map[i][j]=='W') wolfList.add(new Point(i, j));
            }
        }
        
        //늑대가 양이 있는 칸으로 갈 수 없게 할 수 있다면
        if(canBlockWolf(sheepList)){
            System.out.println(1);
            
            makeFenceToWolf(wolfList);//늑대 주위로 울타리를 둘러 싼다.
            
            for(int i=0; i<r; i++) {
                for (int j = 0; j < c; j++) {
                    System.out.print(map[i][j]);
                }
                System.out.println();
            }
        }else { //늑대를 막는게 불가능 하다면
            System.out.println(0);
        }
    }

    //늑대의 상하좌우에 울타리를 배치한다.
    private static void makeFenceToWolf(ArrayList<Point> wolfList) {
        for (Point wolf : wolfList) {
            for(int i=0; i<4; i++) {
                int nr = wolf.r + dr[i];
                int nc = wolf.c + dc[i];
                //목장을 벗어나면 continue
                if (nr >= r || nr < 0 || nc >= c || nc < 0) continue;
                //주의, 늑대가 있는 경우는 울타리를 배치할 수 없다.
                if(map[nr][nc]=='.')map[nr][nc] = 'D';
            }
        }
    }
    
    //늑대를 막는 것이 가능한지 판단하는 함수
    static boolean canBlockWolf(ArrayList<Point> sheepList){
        for (Point sheep : sheepList) {
            for(int i=0; i<4; i++){
                int nr = sheep.r+dr[i];
                int nc = sheep.c+dc[i];

                //목장을 벗어나면 continue
                if(nr>=r || nr<0 || nc>=c || nc<0) continue;
                //양의 상하좌우에 늑대가 존재한다면, 늑대를 막는것이 불가능하다
                if(map[nr][nc]=='W') return false;
            }
        }
        return true;
    }
}