📣
Baekjoon에서 PASS된 코드만 업데이트합니다.
알고리즘을 먼저 풀이하는 언어(Java)가 정해져있어,
풀이 언어(Python, C++, Java)가 모두 업데이트될 때까지는 시간이 걸릴 수 있습니다.
문제 제시
문제
크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다.
양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 이동할 수 있다.
두 칸이 인접하다는 것은 두 칸이 변을 공유하는 경우이다.
목장에 울타리를 설치해 늑대가 양이 있는 칸으로 갈 수 없게 하려고 한다.
늑대는 울타리가 있는 칸으로는 이동할 수 없다. 울타리를 설치해보자.
입력
첫째 줄에 목장의 크기 R, C가 주어진다.
둘째 줄부터 R개의 줄에 목장의 상태가 주어진다. '.'는 빈 칸, 'S'는 양, 'W'는 늑대이다.
출력
늑대가 양이 있는 칸으로 갈 수 없게 할 수 있다면 첫째 줄에 1을 출력하고, 둘째 줄부터 R개의 줄에 목장의 상태를 출력한다. 울타리는 'D'로 출력한다. 울타리를 어떻게 설치해도 늑대가 양이 있는 칸으로 갈 수 있다면 첫째 줄에 0을 출력한다.
제한
- 1 ≤ R, C ≤ 500
문제 풀이
문제의 입출력 예시를 보고 풀려고 하면 매우 어려워집니다.
저 역시 이 문제의 입력값에 대해서 출력값이 어떻게 나오게 되는 건지 꽤 오래 고민했습니다.
이 문제 분류는 스페셜 저지입니다!
출력 값이 예시처럼이 아닌 다양한 경우로 나와도 됩니다.
즉, 유무를 판단하는 0과 1의 출력값을 제외한, 목장에 대한 정보는 전혀 다르게 나와도 괜찮은 것이죠.
이렇게 되면 접근이 조금 더 쉬워집니다.
현재 문제의 울타리의 수는 제한이 없으며, 몇개를 넣어도 무관한 것이죠.
따라서 늑대의 정보를 저장하고 4방을 확인하면서 검사하는 방식을 적용할 것입니다.
이렇게 검사를 하는 중에 발생할 수 있는 상황은 총 4가지 입니다.
- 양('S')이 있는 경우 : 바로 0을 출력하면 됩니다.
- 늑대('W')가 있는 경우 : 늑대도 무조건 1마리라는 보장이 없으며, 늑대 옆에 늑대가 있을 수 있습니다.늑대와 늑대는 서로의 간섭대상이 아니므로 무시합니다.
- 울타리('D')가 있는 경우 : 이미 제한되어있으므로, 늑대는 더 확인할 수 없어 다음 방향을 확인합니다.
- 빈칸('.')인 경우 : 무조건 울타리를 설치하는 대상이 됩니다.
빈칸이 인접하면 무조건 울타리를 설치하는 것은 늑대를 1x1m의 공간에 가두는 것입니다.
인정머리 없지만... 양을 지켜야죠! 🐏 ㅎㅎ
이렇게 모든 늑대의 주위를 확인하며 울타리를 선택하는데 양을 만나지 않고 끝난다면,
늑대를 안전하게 모두 가둔 것입니다.
이 상태의 목장 정보를 함께 출력하면 되겠습니다.
- 늑대 정보 : Class 형식으로 저장
- 늑대들의 정보 : Queue형식으로 저장
- 모든 정보 확인 : Delta 활용
문제 코드
Java
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int R, C;
static char[][] map;
static Queue<Walf> list = new LinkedList<Walf>();
public static void main(String[] args) throws Exception{
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++) {
String str = br.readLine();
for(int j=0;j<C;j++) {
map[i][j] = str.charAt(j);
if(map[i][j] == 'W')
list.add(new Walf(i, j));
}
}
StringBuffer sb = new StringBuffer();
boolean result = close();
sb.append(result?1:0);
if(result) {
sb.append("\n");
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.toString());
}
private static void printArr(char[][] arr) {
for (int i = 0; i < arr.length; i++)
System.out.println(Arrays.toString(arr[i]));
}
static int[][] DELTA = {{0,1},{0,-1},{1,0},{-1,0}};
private static boolean close() {
if(list.isEmpty())
return true;
else {
int n = list.size();
for(int i=0;i<n;i++) {
Walf w = list.poll();
int x = w.x;
int y = w.y;
for(int d=0;d<4;d++) {
int nx = x+DELTA[d][0];
int ny = y+DELTA[d][1];
if(nx < 0 || nx>=R||ny<0||ny>=C)
continue;
if(map[nx][ny] == 'D'||map[nx][ny] == 'W')
continue;
else if(map[nx][ny] == 'S')
return false;
map[nx][ny] = 'D';
}
}
return true;
}
}
static class Walf {
public int x;
public int y;
public Walf(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
}제출 결과
