[백준] #13460 구슬 탈출 2 (Java) (feat. 구현 문제 접근법)

주재완·2024년 2월 7일
BFS구현그래프백준
0

백준

목록 보기
5/8
post-thumbnail

중요하거나 어려웠던 문제에 대해서 작성합니다.

삼성 SW 역량 테스트 기출 문제
구현 / 그래프 이론 / 그래프 탐색 / 시뮬레이션 / BFS

구현 및 시뮬레이션류가 멀리 보면 재밌는데 실제 만난다 하면 아직까진 아찔하긴 하다. 연습 많이 해야겠다는 생각이 든다. 이미 했던 문제들도 지금 풀면 어려울 수 있으니 꺼진 불도 다시 보도록 하자. 아래처럼 좀 많이 틀리기는 했다...

문제 📝 (Gold 1)

단순히 보면 재밌는 문제인데, 구현이 많이 힘들었어서 선정하게 되었다. 공이 1개면 실버 상위 골드 하위였겠지만, 공이 두 개가 되니 난이도가 확 높아졌다. 문제는 다음 링크를 참고하기 바란다.

접근방법

알려진대로 삼성 SW 역량 테스트 문제이다보니 구현이 힘든 편이긴 하다. 구현 문제를 풀면서 나름대로 정리해본 접근 방법은 다음과 같다.

  1. 우선 문제가 이해가 안되면 테스트 케이스를 통해서 직접 손으로 풀어본다.
  2. 문제에서의 조건들을 요약해본다. 이 때 그림을 적극 활용한다.
  3. 각 조건들을 메소드(함수)를 만들어서 구현해본다. 이 때, 어떤 알고리즘을 적용할지 생각해보고 가능하면 시간 복잡도도 함께 생각해보자.
  4. (특히 공부시에는) 디버깅을 적극적으로 활용한다.
  5. 반례들을 생각해보자. 반례는 최대한 극단적인 케이스로 생각하자.

사실 구현 문제 뿐만이 아닌 모든 문제에 해당하는 케이스라 생각한다. 그런데 특히 구현이 힘든 문제가 이렇게 생각해보는게 더 중요하다 생각한다.

1. 테스트 케이스 보기

다행히도 테스트 케이스가 꽤 많아서 문제 이해하는데 큰 도움을 주었을꺼라 생각한다. 예제 1, 2를 통해 어떤 상황인지 알아보자.

예제 1

5 5
#####
#..B#
#.#.#
#RO.#
#####

오른쪽으로 기울이면 빨간 구슬(R)이 오른쪽으로 굴러가면서 1번만에 탈출 성공하게 된다.

#####
#..B#
#.#.#
#.O.#
#####

예제 2

7 7
#######
#...RB#
#.#####
#.....#
#####.#
#O....#
#######

탈출까지 직접하면 5번이 걸리는데, 이 예제를 통해 한가지 사실을 알 수 있다. 일단 당연하겠지만 왼쪽으로 밖에 이동이 안되므로 왼쪽으로 기울여보면 아래와 같다.

#######
#RB...#
#.#####
#.....#
#####.#
#O....#
#######

코드로써 구현해야되는 부분을 확인할 수 있는게, 어떻게 기울이든 간에 빨간색 공 위치(이하 R)와 파란색 공 위치(이하 B)는 겹치치 않는다는 것이다. 이 문제의 핵심 구현 부분이라고 할 수 있다.

예제 7

안되는 케이스 역시 살펴볼 필요가 있다.

3 10
##########
#.O....RB#
##########

직관적으로도 왼쪽으로 기울여야 되는 것을 알 수 있다. 하지만 그럴 경우 R과 B는 구멍 O를 지나가게 되어서 문제 조건을 만족하지 않고, 나머지 방향으로 못가므로 10번 이내에 문제를 해결할 수 없다. 즉 -1이 나오게 된다.

2. 문제 조건 요약

테스트 케이스를 통한 문제 조건은 다음과 같다.

  1. (입출력) #은 이동 불가능, .은 이동 가능, O는 이동 가능하지만 빠지는 구멍
  2. 보드를 기울이면 갈 수 있는 끝까지 움직인다.
  3. R이 탈출할 때 B가 탈출하면 안된다.
  4. R과 B의 위치는 겹치지 않는다.
  5. 시뮬레이션은 총 10번 진행된다.

아래 조건 구현에서 각각 하나씩 해보도록 하자.

3. 조건 구현

3-0. 입출력

입출력은 main() 메소드에서 진행한다.
우선 각 공의 위치가 필요하므로, 이를 Ball로 만들어 놓자. cnt는 해당 볼이 움직이 횟수를 의미한다.

...
static class Ball {
	int row;
	int col;
	int cnt;
		
	public Ball(int row, int col, int cnt) {
		this.row = row;
		this.col = col;
		this.cnt = cnt;
	}
}
...

그리고 움직일 수 있는 케이스와 움직이지 못하는 케이스로 분리해서 해결해보자.

  • 해당 칸으로 움직일 수 있는 케이스 : 해당 칸이 '.', 'O'
  • 해당 칸으로 움직일 수 없는 케이스 : 해당 칸이, '#', R의 경우 B, B의 경우 R

공의 종류에 따라 케이스가 나눠짐을 확인할 수 있다. 이럴 경우 일일이 조건문으로 처리도 가능하지만, 부분적으로 움직이는게 가능하므로 일단 '.'으로 처리하고 나중에 위치를 처리하는 것이 좀 더 좋아보인다.

즉 조건이 많아지면 처리하기 힘들어진다. 이를 최대한 단순하게 '#'(갈 수 없음) 과 '.'(갈 수 있음) 으로 최대한 묶고, 특수한 케이스(구멍, 공)은 좌표를 따로 저장해두자.

아래에서는 구멍 O는 holeRow, holeCol로 저장하였고, 공은 Ball 객체를 사용하였다.

...
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
StringTokenizer st;
		
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
board = new char[n][m]; // static char[][] board; 
isOut = new boolean[2]; // static boolean[];
Ball[] balls = new Ball[2]; // 인덱스 0 : R, 인덱스 1 : B
		
int ans = -1;
		
for(int i = 0; i < n; i++) {
	String row = br.readLine();
	for(int j = 0; j < m; j++) {
		char c = row.charAt(j);
				
		if(c == 'R') {
			balls[0] = new Ball(i, j, 0); // 우선 Ball 객체 생성한다.
			board[i][j] = '.';	// 갈 수 있는 케이스로 지정
		} else if(c == 'B') {
			balls[1] = new Ball(i, j, 0); // 우선 Ball 객체 생성한다.
			board[i][j] = '.'; // 갈 수 있는 케이스로 지정
		} else if(c == 'O') {
			holeRow = i;
			holeCol = j; // 구멍의 좌표 저장
			board[i][j] = '.'; // 갈 수 있는 케이스로 지정
		} else {
			board[i][j] = c;
		}
	}
}
...

3-1. 보드를 기울이면 갈 수 있는 끝까지 움직인다.

조건을 살펴보면, 움직일 수 있는 곳은 .이므로 .이 있는 곳은 다 움직일 수 있다. 다만 R의 경우 B를 만나면 일종의 벽이 되어서 진행할 수 없다. 그리고 B의 경우는 반대로 R을 만날 때 그렇다. 그러면 아래와 같은 방법으로 코드를 짜면 될 것이라 생각 가능하다.

  • 우선 R에 대해서 진행하고 다음은 B에 대해서 진행한다. (순서 바꿔도 무관)
  • 공이 구를 때 이동하는 방법은 아래와 같이 클래스 변수 만들어서 for 문으로 돌리는 방법이 가장 일반적이다.
...
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
...
  • 상하좌우 각각으로 탐색하는 것이 적합하다. Queue를 만들어 bfs를 진행한다.
  • 한칸 가는 것은 현재 위치에서 dr[i]를 지속적으로 더해야 한다.
    • 언제까지? (벽에 닿을 때 or 다른 공 좌표에 닿을 때) 직전까지!

우선 굴러가는 것을 구현해보자.

// rolling(방향, 공 인덱스(다른 공은 1 - rbIdx로 확인 가능), 공, 다른 공)
public static int[] rolling(int i, int rbIdx, int[] ballPos, int[] otherBallPos) {
	int ballRow = ballPos[0], ballCol = ballPos[1];
	int otherBallRow = otherBallPos[0], otherBallCol = otherBallPos[1];
	while(board[ballRow + dr[i]][ballCol + dc[i]] == '.') { // 갈 수 있을 때
		// 만일 다른 공이 나갔을 때 && 해당 공이 다른 공 좌표에 도달 할 때 -> 멈춤
        if(!isOut[1- rbIdx] && ballRow + dr[i] == otherBallRow && ballCol + dc[i] == otherBallCol) break;
			
		isNotMoved = false; // 안움직이면 구지 큐에 넣을 필요가 없다.
		
        // 이상 없으면 계속 이동
		ballRow += dr[i];
		ballCol += dc[i];
		
        // 이동 후 공이 나갔는지 확인
		if(ballRow == holeRow && ballCol == holeCol) isOut[rbIdx] = true;
	}
	return new int[] {ballRow, ballCol};
}

3-2. R이 탈출할 때 B가 탈출하면 안된다.

조건문으로 간단하게 처리가 가능하다.

...
if(isOut[1]) { // B가 빠지면 볼 것도 없다. 그냥 무시하자.
	continue;
} else if(isOut[0]) { // B는 안빠졌는데 A가 빠졌다면 그게 바로 우리가 찾는 케이스이다.
	flag = true;
    // int ans = -1로 bfs 시작 전에 초기화해준다.
	ans = nextRed.cnt; // 만약 이것을 안거칠 경우 ans = -1이 되게 된다.
	break;
}
...

추가적으로 if(isNotMoved) continue;를 적어줘서 모두 움직이지 않는 케이스는 무시해서 메모리를 조금이라도 아껴보자.

3-3. R과 B의 위치는 겹치지 않는다.

이 문제의 핵심이다. 만일 3-1 코드를 진행할 경우 다음과 같은 상황을 만나게 된다. 우선 최대한 간단한 사례를 보자. (편의상 구멍은 제거하였다.)

######
#..BR#
######

아주 간단한 사례이다. 그런데 왼쪽으로 기울인 것을 구현하면 3-1 코드만 진행할 경우 다음과 같이 움직인다.

######
#B..R#
######

우리의 직관과는 달리 B만 움직인다. 그 이유는 우리가 R부터 움직이는 것을 구현하였는데, 처음 R의 경우 왼쪽에 B가 있어 더 이상 움직이지 못하기 때문이다. 그러면 어떻게 해야될까?

방법은 매우 간단하다. 한번 더 움직이면 된다. 공들 중 하나는 이미 움직임을 완료했기에 남은 하나에 대해서만 추가로 한번 움직이면 최종적인 위치가 나올 것이다.

그런데, 그 남은 하나가 뭔지 어떻게 알 수 있을까? 모르기 때문에 일단 둘 다 반복문을 똑같이 돌린다.

남은 과제는 해당 공에 대해서 언제 반복문을 돌려야 하는지 따져야 된다. 우선 반복문이 필요 없는 경우는 다음과 같다.

  • 일단 해당 공이 밖으로 나가면 반복문이 필요가 없다.
    isOut[i]
  • 다음으로 움직이지 못하는 공은 반복문이 필요가 없다.
    board[nextPos[0] + dr[i]][nextPos[1] + dc[i]] != '.'

이 두 조건이 전부인 것을 알 수 있다. 이 두 조건이 아닌 경우는 반복문이 필요하다.

....
if(!isOut[0] && board[nextRedPos[0] + dr[i]][nextRedPos[1] + dc[i]] == '.') {
	nextRedPos = rolling(i, 0, nextRedPos, nextBluePos);
}
				
if(!isOut[1] && board[nextBluePos[0] + dr[i]][nextBluePos[1] + dc[i]] == '.') {
	nextBluePos = rolling(i, 1, nextBluePos, nextRedPos);
}
....

3-4 시뮬레이션은 총 10번 진행된다.

이건 간단하다. 빨간공.cnt 가 10일 때는 종료해준다. 물론 Queue에 넣을 때마다 cnt+1 해주는 것은 절대 잊지 말자.

Java ☕️

import java.io.*;
import java.util.*;

public class Main {
	static class Ball {
		int row;
		int col;
		int cnt;
		
		public Ball(int row, int col, int cnt) {
			this.row = row;
			this.col = col;
			this.cnt = cnt;
		}
	}
	
	static int holeRow, holeCol;
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	static char[][] board;
	static boolean isNotMoved;
	static boolean[] isOut;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		board = new char[n][m];
		isOut = new boolean[2];
		Ball[] balls = new Ball[2];
		
		int ans = -1;
		
		for(int i = 0; i < n; i++) {
			String row = br.readLine();
			for(int j = 0; j < m; j++) {
				char c = row.charAt(j);
				
				if(c == 'R') {
					balls[0] = new Ball(i, j, 0);
					board[i][j] = '.';
				} else if(c == 'B') {
					balls[1] = new Ball(i, j, 0);
					board[i][j] = '.';
				} else if(c == 'O') {
					holeRow = i;
					holeCol = j;
					board[i][j] = '.';
				} else {
					board[i][j] = c;
				}
			}
		}
		
        Queue<Ball[]> q = new LinkedList<>();
		q.add(balls);
		
		while(!q.isEmpty()) {
			Ball[] now = q.poll();
			Ball nowRed = now[0];
			Ball nowBlue = now[1];
			boolean flag = false;
			
			if(nowRed.cnt >= 10) break;
			
			for(int i = 0; i < 4; i++) {
				isOut[0] = false;
				isOut[1] = false;
				isNotMoved = true;
				
				int[] nextRedPos = {nowRed.row, nowRed.col};
				int[] nextBluePos = {nowBlue.row, nowBlue.col};
				
				nextRedPos = rolling(i, 0, nextRedPos, nextBluePos);
				nextBluePos = rolling(i, 1, nextBluePos, nextRedPos);
				
				if(!isOut[0] && board[nextRedPos[0] + dr[i]][nextRedPos[1] + dc[i]] == '.') {
					nextRedPos = rolling(i, 0, nextRedPos, nextBluePos);
				}
				
				if(!isOut[1] && board[nextBluePos[0] + dr[i]][nextBluePos[1] + dc[i]] == '.') {
					nextBluePos = rolling(i, 1, nextBluePos, nextRedPos);
				}
				
				if(isNotMoved) continue;
				
				Ball nextRed = new Ball(nextRedPos[0], nextRedPos[1], nowRed.cnt + 1);
				Ball nextBlue = new Ball(nextBluePos[0], nextBluePos[1], nowBlue.cnt + 1);
				
				if(isOut[1]) {
					continue;
				} else if(isOut[0]) {
					flag = true;
					ans = nextRed.cnt;
					break;
				}
				
				q.add(new Ball[] {nextRed, nextBlue});
			}
			
			if(flag) break;
		}
		
		System.out.println(ans);
		br.close();
	}
	
	public static int[] rolling(int i, int rbIdx, int[] ballPos, int[] otherBallPos) {
		int ballRow = ballPos[0], ballCol = ballPos[1];
		int otherBallRow = otherBallPos[0], otherBallCol = otherBallPos[1];
		while(board[ballRow + dr[i]][ballCol + dc[i]] == '.') {
			if(!isOut[1- rbIdx] && ballRow + dr[i] == otherBallRow && ballCol + dc[i] == otherBallCol) break;
			
			isNotMoved = false;
			
			ballRow += dr[i];
			ballCol += dc[i];
			
			if(ballRow == holeRow && ballCol == holeCol) isOut[rbIdx] = true;
		}
		return new int[] {ballRow, ballCol};
	}
}
profile
주재완
언제나 탐구하고 공부하는 개발자, 주재완입니다.
이전 포스트

[백준] 가장 긴 증가하는 부분 수열 시리즈 - 자바

다음 포스트

[백준] #1018 체스판 다시 칠하기

0개의 댓글