[백준] 16956 늑대와 양(Java)
문제링크
문제분석
- 목장의 각칸은 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;
}
}
Author And Source
이 문제에 관하여([백준] 16956 늑대와 양(Java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ash753/백준-16956-늑대와-양Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)