문제
창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.
동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.
창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다. 막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다.
막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.
미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다. 새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다. 떨어지는 동안 클러스터의 모양은 변하지 않는다. 클러스터는 다른 클러스터나 땅을 만나기 전까지 게속해서 떨어진다. 클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다.
동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 동굴의 크기 R과 C가 주어진다. (1 ≤ R,C ≤ 100)
다음 R개 줄에는 C개의 문자가 주어지며, '.'는 빈 칸, 'x'는 미네랄을 나타낸다.
다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100)
마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어져 있다. 모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다. 첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.
공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다.
출력
입력 형식과 같은 형식으로 미네랄 모양을 출력한다.
입출력 예
풀이
- 높이와 방향에 맞는 미네랄 제거
- 바닥에 붙어 있는 클러스터를 방문
- 2에서 방문하지 않은 클러스터를 아래로 이동
- 모든 턴이 끝날 때까지 1~3과정 반복
코드
import java.io.*;
import java.util.*;
public class Main_B18500 {
static char[][]map;
static int R,C;
static boolean[][] vistied;
static int[]dx= {1,-1,0,0};
static int[]dy= {0,0,1,-1};
static Queue<int[]>cluster=new LinkedList<>();;
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st=new StringTokenizer(br.readLine());
StringBuilder sb=new StringBuilder();
R=Integer.parseInt(st.nextToken());
C=Integer.parseInt(st.nextToken());
map=new char[R][C];
for(int i=0;i<R;i++)map[i]=br.readLine().toCharArray();
int cnt=Integer.parseInt(br.readLine());
st=new StringTokenizer(br.readLine());
for(int t=0;t<cnt;t++){
int height=R-Integer.parseInt(st.nextToken());
remove(t%2,height);
vistied=new boolean[R][C];
//바닥에 있는 미네랄 모두 방문 체크
for(int i=0;i<C;i++) {
if(map[R-1][i]=='x'&&!vistied[R-1][i])
bfs(R-1,i);
}
boolean downCheck=false;
//공중에 있는 클러스터를 찾아 아래로
//문제에서 1개이하의 클러스터만 떨어진다고 했으므로 하나가 떨어지면 반복문 종료
for(int i=0;i<R;i++) {
if(downCheck)break;
for(int j=0;j<C;j++) {
if(map[i][j]=='x'&&!vistied[i][j]) {
bfs(i,j);
down();
downCheck=true;
break;
}
}
}
}
for(char[]a:map) {
for(char c:a) {
sb.append(c);
}
sb.append("\n");
}
bw.write(sb.toString());
bw.flush();
}
//높이와 방향에 따라 미네랄 파괴
static void remove(int d,int height) {
int i=0;
if(d==0) {
for(i=0;i<C;i++) {
if(map[height][i]=='x') {
map[height][i]='.';
break;
}
}
}
else {
for(i=C-1;i>=0;i--) {
if(map[height][i]=='x') {
map[height][i]='.';
break;
}
}
}
}
//클러스터 찾기
static void bfs(int x,int y) {
Queue<int[]>q=new LinkedList<>();
cluster.clear();
cluster.add(new int[] {x,y});
q.add(new int[] {x,y});
vistied[x][y]=true;
while(!q.isEmpty()) {
int[]temp=q.poll();
for(int i=0;i<4;i++) {
int nx=temp[0]+dx[i];
int ny=temp[1]+dy[i];
if(nx>=0&&ny>=0&&nx<R&&ny<C&&!vistied[nx][ny]&&map[nx][ny]=='x') {
vistied[nx][ny]=true;
cluster.add(new int[] {nx,ny});
q.add(new int[] {nx,ny});
}
}
}
}
//분리되어 있는 클러스터를 아래로 이동
static void down() {
int[][]temp=new int[cluster.size()][2];
int i=0,minus=0,size=temp.length;
while(!cluster.isEmpty()) {
temp[i++]=cluster.poll();
}
change(0, size, temp, '.');
while(true) {
if(check(minus+1, size, temp))minus++;
else break;
}
change(minus, size, temp, 'x');
}
//map 상태 변경
static void change(int minus,int size,int[][] temp,char c) {
for(int i=0;i<size;i++) {
int nx = temp[i][0]+minus;
int ny = temp[i][1];
map[nx][ny]=c;
}
}
//내려갈 수 있는지 확인
static boolean check(int minus,int size,int[][] temp) {
for(int i=0;i<size;i++) {
int nx = temp[i][0]+minus;
int ny = temp[i][1];
if(nx>=R||map[nx][ny]=='x') return false;
}
return true;
}
}
