지금 크롬 확장 프로그램 손상이 계속 나고, 삭제는 계속 안되고, 의 반복이다.. 새로운 방법 다써봤는데, 다시 시작하면 또 같은 문제의 반복이다.. 도데체 뭐가 문젠지...
구슬 탈출 2 는 어려운 시뮬레이션 문제로, 푸는데 몇시간이 걸렸는지 모르겠다... 제출만 8번을 하면서..모르겠다..
코드 갈아 엎는 것만 두번 했다..
그리고.. 런타임 에러가 떳는데. submit_java 크롬 확장 프로그램이 안먹어서 다시 치려다보니..package를 안지워 준 것이 문제였다..
그리고 한 57%? 50퍼 대에서 한번 틀렸습니다가 떴는데, 10까지가 아니라 11까지 제출 할 수 있게 해 두었기 때문이었다. 10이면 멈춰야 했는데, 11에서 멈췄다..
그리고 갈아엎은 것이 구슬을 돌릴때의 같은 위치에 멈출 경우의 문제라, 한번 코드를 싹 갈았다...
이 문제는 정말 생각할 포인트가 많은 문젠데,
정확한 포인트를 잡지 ㅇ낳고서는 한번에 풀기 여간 힘든게 아닌가 싶다.
포인트는
1. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.
2. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패
3. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다.
이 세가지를 잘 잡고 문제를 풀어야 이를 해결할 수 있다. 특히 3번이 정말 코드를 짜는데 헷갈렸다.
테케가 맞는데도, 안풀리는 경우가 너무 힘들었다..ㅠㅜ
문제
스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.
보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.
이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.
각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.
입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.
문제 설명은 짧다.. 그림이나 예시가 있으면 이해하기 쉬웠을 지도.. 라는 생각도 든다.
밑으로는 코드를 첨부하고, 설명을 진행하겠다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class 구슬탈출2 {
static int ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int RI=0,RJ=0, BI=0, BJ=0;
char[][] arr = new char[N][M];
for (int i = 0; i < N; i++) {
arr[i] = br.readLine().trim().toCharArray();
for (int j = 0; j < M; j++) {
if(arr[i][j]=='R') {
RI =i;
RJ = j;
arr[i][j] ='.';
}else if(arr[i][j] == 'B') {
BI = i;
BJ = j;
arr[i][j] ='.';
}
}
}
// 1 상, 2 하 , 2 좌, 3 우
Queue<int[]> q = new LinkedList<int[]>();
q.add(new int[] {RI,RJ,BI,BJ,0,0});
while(true) {
int[] t = q.poll();
if(t[4]>=10) {
break;
}
if(t[5]!=1) {
int ri = t[0],rj = t[1],bi=t[2],bj=t[3];
while(true) {
if(arr[bi-1][bj]=='O') {
bi--;
break;
}else if(arr[bi-1][bj]=='#') {
break;
}
bi--;
}
while(true) {
if(arr[ri-1][rj]=='O') {
ri--;
break;
}else if(arr[ri-1][rj]=='#') {
break;
}
ri--;
}
if(arr[bi][bj]!='O') {
if(arr[ri][rj]=='O') {
System.out.println(t[4]+1);
System.exit(0);
}else {
if(ri==bi && rj==bj) {
if(t[0]>t[2])ri++;
else bi++;
}
q.add(new int[] {ri,rj,bi,bj,t[4]+1, 1});
}
}
}
if(t[5]!=2) {
int ri = t[0],rj = t[1],bi=t[2],bj=t[3];
while(true) {
if(arr[bi+1][bj]=='O') {
bi++;
break;
}else if(arr[bi+1][bj]=='#') {
break;
}
bi++;
}
while(true) {
if(arr[ri+1][rj]=='O') {
ri++;
break;
}else if(arr[ri+1][rj]=='#') {
break;
}
ri++;
}
if(arr[bi][bj]!='O') {
if(arr[ri][rj]=='O') {
System.out.println(t[4]+1);
System.exit(0);
}else {
if(ri==bi && rj ==bj) {
if(t[0]<t[2])ri--;
else bi--;
}
q.add(new int[] {ri,rj,bi,bj,t[4]+1, 2});
}
}
}
if(t[5]!=3) {
int ri = t[0],rj = t[1],bi=t[2],bj=t[3];
while(true) {
if(arr[bi][bj-1]=='O') {
bj--;
break;
}else if(arr[bi][bj-1]=='#') {
break;
}
bj--;
}
while(true) {
if(arr[ri][rj-1]=='O') {
rj--;
break;
}else if(arr[ri][rj-1]=='#') {
break;
}
rj--;
}
if(arr[bi][bj]!='O') {
if(arr[ri][rj]=='O') {
System.out.println(t[4]+1);
System.exit(0);
}else {
if(ri==bi && rj==bj) {
if(t[1]>t[3])rj++;
else bj++;
}
q.add(new int[] {ri,rj,bi,bj,t[4]+1, 3});
}
}
}
if(t[5]!=4) {
int ri = t[0],rj = t[1],bi=t[2],bj=t[3];
while(true) {
if(arr[bi][bj+1]=='O') {
bj++;
break;
}else if(arr[bi][bj+1]=='#') {
break;
}
bj++;
}
while(true) {
if(arr[ri][rj+1]=='O') {
rj++;
break;
}else if(arr[ri][rj+1]=='#') {
break;
}
rj++;
}
if(arr[bi][bj]!='O') {
if(arr[ri][rj]=='O') {
System.out.println(t[4]+1);
System.exit(0);
}
if(ri==bi && rj==bj) {
if(t[1]<t[3])rj--;
else bj--;
}
q.add(new int[] {ri,rj,bi,bj,t[4]+1, 4});
}
}
}
System.out.println(-1);
}
}
1. 데이터 받기
여기에서 구슬이 원래 있었던 위치를 '.'으로 변경해 주었다. 구슬이 한 위치에 있으면 안되면서 동시에 굴러가기 때문에 구슬의 위치는 따로 저장해 두고, 이후 같은 위치라면 처리를 해주는 과정이 더 편리하게 적용되었다.
2. 구슬 굴리기
현재 구슬의 위치를 중심으로 구슬을 상, 하, 좌,우 (1,2,3,4)로 굴려주었다.
Queue를 통해 BFS를 도는 코드를 이용하였다. 그러면 더 차례대로 돌기 때문에 최소값을 찾기가 더 빠를 것이라고 생각하였다.
같은 방향으로 계속 기울일 경우 구슬의 아무런 이동도 없기 때문에, 이전의 구르는 방향을 미리 q에 넣는 리스트에 같이 넣어 주었다.
queue에는 , 빨간구슬i, 빨간구슬j, 파란구슬i, 파란구슬 j, 굴린 횟수, 방향 이 들어간다.
3. 구멍에 빠졌나 확인
검은 구슬 B가 구멍에 빠지면 안되기 떄문에, 미리 arr[bi][bj]를 통해 구슬이 구멍에 있는 지 아닌지를 확인해 준다.
이후 없고, arr[ri][rj]=='O'라면 빨간 구슬이 구멍에 빠진 것이므로, 또한 bfs로 인하여 최소값으로 회전하고 있으므로, 출력하고, 시스템을 종료해준다.
함수를 선언하여 돌려 주었다면 return으로 선언해도 되었지만, 지금은 main 함수 내에서 모든 기능을 돌리기 있기 때문에, 시스템을 바로 종료해 주었다.
그렇지 않다면 queue에 넣어 계속 구슬 상자를 움직일 수 있게 해주어야 하는데,
이를 검사하기 이전에 구슬이 같은 위치에 있는 지 확인하고 같은 위치에 있다면, 이전의 초기값 t에서 구슬의 각 위치를 확인하여 위의 경우는 위로 기울기 때문에, 더 아래쪽에 있었던, 구슬을 아래로 한칸 미뤄주게 된다.
4. 다른 방법으로 구슬 굴리기.
이후 현재값과 , 방향, 그리고 도는 횟수를 추가하여 계속 BFS로 구슬을 이동시킬 수 있게 한다.
bfs루프를 빠져나오는 경우는 10을 초과하는 경우가 되도록,
하고, 마지막에 print를 통해 -1을 출력해준다.
진짜 한 2시간 주면 이런문제는 너무 힘들어서 못풀거 같다..ㅎㅎ.. 더 연습하도록 해야지..
'코딩테스트 연습 > 백준' 카테고리의 다른 글
| [ 백준 / 16235 ] 나무재테크 : java (0) | 2020.08.16 |
|---|---|
| [ 백준 / 19237 ] 어른상어 : java (0) | 2020.07.20 |
| [ 백준 / 17406 ] 배열돌리기4 - java (0) | 2020.07.09 |
| [ 백준 17281번 ] Gold IV - ⚾ ( 야구) - 자바 (0) | 2020.07.04 |
| [ 백준 / 19238번 ] Gold IV - 스타트 택시 ( java ) (0) | 2020.06.29 |
