알고리즘||코딩테스트/삼성 SW 역량테스트
[BOJ 13460] 구슬 탈출 2 - JAVA, Gold1
째로스
2023. 12. 19. 15:00
https://www.acmicpc.net/problem/13460
13460번: 구슬 탈출 2
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'
www.acmicpc.net
📌구현할 기능 목록
1. 직사각형 맵의 크기와 맵의 좌표별 위치 정보를 입력받는다.
- R, B, O 값을 입력받았을 경우, 해당 좌표값을 별도의 배열에 저장한다.
2. 1~10번 기울여 이동하여 조건에 만족하는 결과가 나오도록 DFS 함수를 구현한다.
- 한번의 테스트 케이스를 마치면, 맵 정보와 빨간공, 파란공의 위치 좌표를 초기화하는 함수를 작동시킨다.
3. 특정 방향으로 기울일 경우 빨간공과 파란공이 이동할 수 없을 때까지 이동하는 함수를 작성한다.
- 이동 방향에 따라 빨간공 또는 파란공의 이동 우선순위를 구분하여 이동시킨다.
- 예로 위쪽으로 직사각형을 기울인 경우, 만약 빨간공이 파란공보다 더 위에 존재한다면
빨간공을 파란공보다 먼저 이동시킨 후 파란공을 이동시킨다.(파란공이 더 위에 있다면 파란공부터 이동)
- 파란공이 목적지에 도달하면 해당 이동은 어떠한 경우에도 실패이다.
- 이동할 수 없을때 까지 특정 방향으로 한칸 씩 계속해서 이동한다
- 위 조건들이 만족하는 상태에서 빨간공이 목적지에 도달하면 성공 조건을 만족한다.
4. 조건을 성공적으로 만족하는 최소의 이동횟수를 출력하고 프로그램을 종료시킨다.
- 조건을 만족하는 경우의 수가 없다면 -1을 출력한다.
🛠주요 로직
직사각형을 기울였을 때, 공들이 방향에 맞게 이동하는 함수를 작성하는 것이 문제의 핵심이다.
그 중 가장 실수하기 쉬운 유형은 아래와 같은 유형이다.
위 경우에서 직사각형을 왼쪽으로 기울이면 빨간공과 파란공 두개 모두가 한 번의 기울임으로 목적지에 도달하게 된다.
문제 조건에서 파란공이 목적지에 도달하는 경우 실패라고 명시되었으므로,
빨간공이 목적지에 도착하더라도 실패이다.
[위 맵을 왼쪽으로 기울인 경우 공이 이동하는 과정]
따라서 빨간공이 목적지에 도착하는 즉시 탈출 성공이라는 로직을 구현해서는 안 되며,
기울였을 때 모든 공의 움직임이 없을 때까지 이동 후, 파란공이 목적지에 도달하지 않았으면서
빨간공이 목적지에 도달한 경우에만 탈출 성공이라는 결과를 도출해야 한다.
💻코드 적용
1. 직사각형 맵의 크기와 맵의 좌표별 위치 정보를 입력받는다.
- R, B, O 값을 입력받았을 경우, 해당 좌표값을 별도의 배열에 저장한다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new char[N][M];
originMap = new char[N][M];
for(int i=0;i<N;++i){
String tempMap = br.readLine();
for(int j=0;j<M;++j){
originMap[i][j]=tempMap.charAt(j);
if(originMap[i][j]=='R'){
originRedBallPosition[0]=i;
originRedBallPosition[1]=j;
}
else if(originMap[i][j]=='B'){
originBlueBallPosition[0]=i;
originBlueBallPosition[1]=j;
}
else if(originMap[i][j]=='O'){
goal[0]=i;
goal[1]=j;
}
}
}
2. 1~10번 기울여 이동하여 조건에 만족하는 결과가 나오도록 DFS 함수를 구현한다.
- 한번의 테스트 케이스를 마치면, 맵 정보와 빨간공, 파란공의 위치 좌표를 초기화하는 함수를 작동시킨다.
static void dfs(int depth){
if(depth==maxCount){
init();
if(incline()){
isSuccess=true;
}
return;
}
for(int i=0;i<4;++i){
direction[depth]=i;
dfs(depth+1);
}
}
3. 특정 방향으로 기울일 경우 빨간공과 파란공이 이동할 수 없을 때까지 이동하는 함수를 작성한다.
- 이동 방향에 따라 빨간공 또는 파란공의 이동 우선순위를 구분하여 이동시킨다.
- 예로 위쪽으로 직사각형을 기울인 경우, 만약 빨간공이 파란공보다 더 위에 존재한다면
빨간공을 파란공보다 먼저 이동시킨 후 파란공을 이동시킨다.(파란공이 더 위에 있다면 파란공부터 이동)
- 파란공이 목적지에 도달하면 해당 이동은 어떠한 경우에도 실패이다.
- 이동할 수 없을때 까지 특정 방향으로 한칸 씩 계속해서 이동한다
- 위 조건들이 만족하는 상태에서 빨간공이 목적지에 도달하면 성공 조건을 만족한다.
static boolean incline(){
boolean result=false;
for(int i=0;i<maxCount;++i){
if(direction[i]==0){ // 상
if(redBallPosition[0]<blueBallPosition[0]){
while(true){
int redMx = redBallPosition[0]+dx[0];
int blueMx = blueBallPosition[0]+dx[0];
if(!(map[redMx][redBallPosition[1]]=='.' || map[redMx][redBallPosition[1]]=='O'
|| map[blueMx][blueBallPosition[1]]=='.' || map[blueMx][blueBallPosition[1]]=='O')){
break;
}
if(redMx>=1 && map[redMx][redBallPosition[1]]!='#'){
map[redBallPosition[0]][redBallPosition[1]]='.';
redBallPosition[0]=redMx;
map[redBallPosition[0]][redBallPosition[1]]='R';
}
if(blueMx>=1 && map[blueMx][blueBallPosition[1]]!='#'){
map[blueBallPosition[0]][blueBallPosition[1]]='.';
blueBallPosition[0]=blueMx;
map[blueBallPosition[0]][blueBallPosition[1]]='B';
}
if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
map[goal[0]][goal[1]]='O';
result=true;
}
if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
return false;
}
}
if(result) return true;
}
else{
while(true){
int redMx = redBallPosition[0]+dx[0];
int blueMx = blueBallPosition[0]+dx[0];
if(!(map[redMx][redBallPosition[1]]=='.' || map[redMx][redBallPosition[1]]=='O'
|| map[blueMx][blueBallPosition[1]]=='.' || map[blueMx][blueBallPosition[1]]=='O')){
break;
}
if(blueMx>=1 && map[blueMx][blueBallPosition[1]]!='#'){
map[blueBallPosition[0]][blueBallPosition[1]]='.';
blueBallPosition[0]=blueMx;
map[blueBallPosition[0]][blueBallPosition[1]]='B';
}
if(redMx>=1 && map[redMx][redBallPosition[1]]!='#'){
map[redBallPosition[0]][redBallPosition[1]]='.';
redBallPosition[0]=redMx;
map[redBallPosition[0]][redBallPosition[1]]='R';
}
if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
map[goal[0]][goal[1]]='O';
result=true;
}
if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
return false;
}
}
if(result) return true;
}
}
else if(direction[i]==1){ // 우
...(중략)
}
}
}
직사각형을 위쪽으로 기울인 하나의 경우만을 나타냈다.
빨간공과 파란공의 위치에 따라 두 공들 중 더 위에 있는 공을 우선으로 이동시켰다.
4. 조건을 성공적으로 만족하는 최소의 이동횟수를 출력하고 프로그램을 종료시킨다.
- 조건을 만족하는 경우의 수가 없다면 -1을 출력한다.
public static void main(String[] args) throws IOException {
...(생략)
for(int i=1;i<=10;++i){
maxCount=i;
init();
dfs(0);
if(isSuccess){
bw.write(maxCount+"\n");
bw.flush();
bw.close();
return;
}
}
bw.write("-1\n");
bw.flush();
bw.close();
}
⌨제출 코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int N,M;
static char map[][];
static char originMap[][];
static int maxCount=0;
static boolean isSuccess=false;
static int direction[] = new int[10];
static int dx[]={-1,0,1,0}; // 상우하좌
static int dy[]={0,1,0,-1};
static int originRedBallPosition[] = new int[2]; // [0] -> x, [1] -> y
static int originBlueBallPosition[] = new int[2];
static int redBallPosition[] = new int[2]; // [0] -> x, [1] -> y
static int blueBallPosition[] = new int[2];
static int goal[] = new int[2];
static boolean incline(){
boolean result=false;
for(int i=0;i<maxCount;++i){
if(direction[i]==0){ // 상
if(redBallPosition[0]<blueBallPosition[0]){
while(true){
int redMx = redBallPosition[0]+dx[0];
int blueMx = blueBallPosition[0]+dx[0];
if(!(map[redMx][redBallPosition[1]]=='.' || map[redMx][redBallPosition[1]]=='O'
|| map[blueMx][blueBallPosition[1]]=='.' || map[blueMx][blueBallPosition[1]]=='O')){
break;
}
if(redMx>=1 && map[redMx][redBallPosition[1]]!='#'){
map[redBallPosition[0]][redBallPosition[1]]='.';
redBallPosition[0]=redMx;
map[redBallPosition[0]][redBallPosition[1]]='R';
}
if(blueMx>=1 && map[blueMx][blueBallPosition[1]]!='#'){
map[blueBallPosition[0]][blueBallPosition[1]]='.';
blueBallPosition[0]=blueMx;
map[blueBallPosition[0]][blueBallPosition[1]]='B';
}
if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
map[goal[0]][goal[1]]='O';
result=true;
}
if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
return false;
}
}
if(result) return true;
}
else{
while(true){
int redMx = redBallPosition[0]+dx[0];
int blueMx = blueBallPosition[0]+dx[0];
if(!(map[redMx][redBallPosition[1]]=='.' || map[redMx][redBallPosition[1]]=='O'
|| map[blueMx][blueBallPosition[1]]=='.' || map[blueMx][blueBallPosition[1]]=='O')){
break;
}
if(blueMx>=1 && map[blueMx][blueBallPosition[1]]!='#'){
map[blueBallPosition[0]][blueBallPosition[1]]='.';
blueBallPosition[0]=blueMx;
map[blueBallPosition[0]][blueBallPosition[1]]='B';
}
if(redMx>=1 && map[redMx][redBallPosition[1]]!='#'){
map[redBallPosition[0]][redBallPosition[1]]='.';
redBallPosition[0]=redMx;
map[redBallPosition[0]][redBallPosition[1]]='R';
}
if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
map[goal[0]][goal[1]]='O';
result=true;
}
if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
return false;
}
}
if(result) return true;
}
}
else if(direction[i]==1){ // 우
if(redBallPosition[1]>blueBallPosition[1]){
while(true){
int redMy = redBallPosition[1]+dy[1];
int blueMy = blueBallPosition[1]+dy[1];
if(!(map[redBallPosition[0]][redMy]=='.' || map[redBallPosition[0]][redMy]=='O'
|| map[blueBallPosition[0]][blueMy]=='.' || map[blueBallPosition[0]][blueMy]=='O')){
break;
}
if(redMy<M-1 && map[redBallPosition[0]][redMy]!='#'){
map[redBallPosition[0]][redBallPosition[1]]='.';
redBallPosition[1]=redMy;
map[redBallPosition[0]][redBallPosition[1]]='R';
}
if(blueMy<M-1 && map[blueBallPosition[0]][blueMy]!='#'){
map[blueBallPosition[0]][blueBallPosition[1]]='.';
blueBallPosition[1]=blueMy;
map[blueBallPosition[0]][blueBallPosition[1]]='B';
}
if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
map[goal[0]][goal[1]]='O';
result=true;
}
if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
return false;
}
}
if(result) return true;
}
else{
while(true){
int redMy = redBallPosition[1]+dy[1];
int blueMy = blueBallPosition[1]+dy[1];
// System.out.println(redBallPosition[0]+" "+redBallPosition[1]);
// System.out.println(blueBallPosition[0]+" "+blueBallPosition[1]);
// System.out.println("========================");
// System.out.println(redBallPosition[0]+" "+redMy);
// System.out.println(blueBallPosition[0]+" "+blueMy);
// System.out.println(redMy+" "+blueMy);
if(!(map[redBallPosition[0]][redMy]=='.' || map[redBallPosition[0]][redMy]=='O'
|| map[blueBallPosition[0]][blueMy]=='.' || map[blueBallPosition[0]][blueMy]=='O')){
break;
}
if(blueMy<M-1 && map[blueBallPosition[0]][blueMy]!='#'){
map[blueBallPosition[0]][blueBallPosition[1]]='.';
blueBallPosition[1]=blueMy;
map[blueBallPosition[0]][blueBallPosition[1]]='B';
}
if(redMy<M-1 && map[redBallPosition[0]][redMy]!='#'){
map[redBallPosition[0]][redBallPosition[1]]='.';
redBallPosition[1]=redMy;
map[redBallPosition[0]][redBallPosition[1]]='R';
}
if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
map[goal[0]][goal[1]]='O';
result=true;
}
if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
return false;
}
}
if(result) return true;
}
}
else if(direction[i]==2){ // 하
if(redBallPosition[0]>blueBallPosition[0]){
while(true){
int redMx = redBallPosition[0]+dx[2];
int blueMx = blueBallPosition[0]+dx[2];
if(!(map[redMx][redBallPosition[1]]=='.' || map[redMx][redBallPosition[1]]=='O'
|| map[blueMx][blueBallPosition[1]]=='.' || map[blueMx][blueBallPosition[1]]=='O')){
break;
}
if(redMx<N-1 && map[redMx][redBallPosition[1]]!='#'){
map[redBallPosition[0]][redBallPosition[1]]='.';
redBallPosition[0]=redMx;
map[redBallPosition[0]][redBallPosition[1]]='R';
}
if(blueMx<N-1 && map[blueMx][blueBallPosition[1]]!='#'){
map[blueBallPosition[0]][blueBallPosition[1]]='.';
blueBallPosition[0]=blueMx;
map[blueBallPosition[0]][blueBallPosition[1]]='B';
}
if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
map[goal[0]][goal[1]]='O';
result=true;
}
if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
return false;
}
}
if(result) return true;
}
else{
while(true){
int redMx = redBallPosition[0]+dx[2];
int blueMx = blueBallPosition[0]+dx[2];
if(!(map[redMx][redBallPosition[1]]=='.' || map[redMx][redBallPosition[1]]=='O'
|| map[blueMx][blueBallPosition[1]]=='.' || map[blueMx][blueBallPosition[1]]=='O')){
break;
}
if(blueMx<N-1 && map[blueMx][blueBallPosition[1]]!='#'){
map[blueBallPosition[0]][blueBallPosition[1]]='.';
blueBallPosition[0]=blueMx;
map[blueBallPosition[0]][blueBallPosition[1]]='B';
}
if(redMx<N-1 && map[redMx][redBallPosition[1]]!='#'){
map[redBallPosition[0]][redBallPosition[1]]='.';
redBallPosition[0]=redMx;
map[redBallPosition[0]][redBallPosition[1]]='R';
}
if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
map[goal[0]][goal[1]]='O';
result=true;
}
if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
return false;
}
}
if(result) return true;
}
}
else if(direction[i]==3){ // 좌
if(redBallPosition[1]<blueBallPosition[1]){
while(true){
int redMy = redBallPosition[1]+dy[3];
int blueMy = blueBallPosition[1]+dy[3];
if(!(map[redBallPosition[0]][redMy]=='.' || map[redBallPosition[0]][redMy]=='O'
|| map[blueBallPosition[0]][blueMy]=='.' || map[blueBallPosition[0]][blueMy]=='O')){
break;
}
if(redMy>=1 && map[redBallPosition[0]][redMy]!='#'){
map[redBallPosition[0]][redBallPosition[1]]='.';
redBallPosition[1]=redMy;
map[redBallPosition[0]][redBallPosition[1]]='R';
}
if(blueMy>=1 && map[blueBallPosition[0]][blueMy]!='#'){
map[blueBallPosition[0]][blueBallPosition[1]]='.';
blueBallPosition[1]=blueMy;
map[blueBallPosition[0]][blueBallPosition[1]]='B';
}
if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
map[goal[0]][goal[1]]='O';
result=true;
}
if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
return false;
}
// printMap();
}
if(result) return true;
}
else{
while(true){
int redMy = redBallPosition[1]+dy[3];
int blueMy = blueBallPosition[1]+dy[3];
if(!(map[redBallPosition[0]][redMy]=='.' || map[redBallPosition[0]][redMy]=='O'
|| map[blueBallPosition[0]][blueMy]=='.' || map[blueBallPosition[0]][blueMy]=='O')){
break;
}
if(blueMy>=1 && map[blueBallPosition[0]][blueMy]!='#'){
map[blueBallPosition[0]][blueBallPosition[1]]='.';
blueBallPosition[1]=blueMy;
map[blueBallPosition[0]][blueBallPosition[1]]='B';
}
if(redMy>=1 && map[redBallPosition[0]][redMy]!='#'){
map[redBallPosition[0]][redBallPosition[1]]='.';
redBallPosition[1]=redMy;
map[redBallPosition[0]][redBallPosition[1]]='R';
}
if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
map[goal[0]][goal[1]]='O';
result=true;
}
if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
return false;
}
}
if(result) return true;
}
}
// printMap();
}
return result;
}
static void printDirection(){
for(int i=0;i<maxCount;++i){
System.out.print(direction[i]+" ");
}
System.out.println();
}
static void printMap(){
System.out.println("=======================");
for(int i=0;i<N;++i){
for(int j=0;j<M;++j){
System.out.print(map[i][j]+" ");
}
System.out.println();
}
System.out.println("=======================");
}
static void dfs(int depth){
if(depth==maxCount){
init();
if(incline()){
isSuccess=true;
}
return;
}
for(int i=0;i<4;++i){
direction[depth]=i;
dfs(depth+1);
}
}
static void init(){
for(int i=0;i<N;++i){
map[i]=originMap[i].clone();
}
redBallPosition[0]=originRedBallPosition[0];
redBallPosition[1]=originRedBallPosition[1];
blueBallPosition[0]=originBlueBallPosition[0];
blueBallPosition[1]=originBlueBallPosition[1];
}
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());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new char[N][M];
originMap = new char[N][M];
for(int i=0;i<N;++i){
String tempMap = br.readLine();
for(int j=0;j<M;++j){
originMap[i][j]=tempMap.charAt(j);
if(originMap[i][j]=='R'){
originRedBallPosition[0]=i;
originRedBallPosition[1]=j;
}
else if(originMap[i][j]=='B'){
originBlueBallPosition[0]=i;
originBlueBallPosition[1]=j;
}
else if(originMap[i][j]=='O'){
goal[0]=i;
goal[1]=j;
}
}
}
for(int i=1;i<=10;++i){
maxCount=i;
init();
dfs(0);
if(isSuccess){
bw.write(maxCount+"\n");
bw.flush();
bw.close();
return;
}
}
bw.write("-1\n");
bw.flush();
bw.close();
}
}