[BOJ] 16956 늑대와 양

문제

www.acmicpc.net/problem/16956

16956번: 늑대와 양

풀이

- BFS 라고 하기엔 애매하지만 늑대 위치를 입력하면서 저장해놓고, 늑대 위치에서만 상,하,좌,우 검사해줬다.

- 네 방향 검사하면서 S가 나오면 어떻게든 막을 수 없는 경우이고, 그 이외엔 D를 찍어주면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Wolf{
    int r,c;
    public Wolf(int r, int c){
        this.r = r;
        this.c = c;
    }
}
public class Main {
    static boolean chk_bdr(int r, int c, int R, int C){
        if((r>=0 && r<R)&&(c>=0&& c<C))
            return true;
        return false;
    }
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<Wolf> list = new ArrayList<>();
        char[][] map;
        int[] dr = {-1,1,0,0}, dc = {0,0,-1,1};
        boolean chk = true;
        int R = Integer.parseInt(st.nextToken()), C = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        for(int i=0;i<R;i++){
            String str = br.readLine();
            for(int j=0;j<C;j++){
                map[i][j] = str.charAt(j);
                if(str.charAt(j)=='W')
                    list.add(new Wolf(i,j));
            }
        }

        //계산
        for(int i=0;i<list.size();i++){
            if(chk){
                Wolf w = list.get(i);
                for(int j=0;j<4;j++){
                    int cr = w.r+dr[j], cc = w.c+dc[j];
                    if(chk_bdr(cr,cc,R,C)){
                        if((map[cr][cc]=='.'))
                            map[cr][cc] = 'D';
                        else if((map[cr][cc]=='S')){
                            chk = false;
                            break;
                        }
                    }
                }
            }
        }

        //출력
        if(chk){
            System.out.println("1");
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    sb.append(map[i][j]);
                }
                sb.append("\n");
            }
            System.out.println(sb);
        }
        else
            System.out.println("0");
    }
}