문제 링크 : https://www.acmicpc.net/problem/13459
코테 스터디에서 풀었던 내용입니다.
스터디 할 때는 PPT를 열심히 작성해서 발표했기 떄문에
스터디 때 풀었던 문제들에 대해서는 그림 자료를 사용합니다!
문제 정의
다음과 같은 그리드가 존재한다고 가정해보겠습니다.
#: 벽.: 이동 가능한 공간O: 구멍R과B: 각각 구슬 색
일 때
파란 구슬을 구멍에 넣지 않으면서 빨간 구슬을
10번 이하로 움직여서
빼낼 수 있으면 1
빼낼 수 없으면 0을 출력한다.
이동 로직
이동 로직은 기존의 BFS 문제와는 다릅니다.
- 구슬이 한 방향으로 1만큼 이동하는 것이 아니라
- 구슬이 한 방향으로 이동할 수 있을 때까지 이동한다는 것입니다.
좌로 한 번 기울인다고 가정하면
구슬들은 벽이나 다른 구슬을 만날 때까지 이동합니다.
문제 조건
문제에서는 한 번 기울이기를 수행했을 때
- 빨간 구슬만 들어가는 경우를 성공이라 간주합니다.
- 위 그림과 같은 상황에서 왼쪽으로 기울일 경우
빨간 구슬과 파란 구슬이 구멍에 동시에 들어가게 되므로 실패로 간주합니다.
접근 방법
두 구슬의 위치 저장
이 문제에서는 두 구슬이 동시에 이동하기 때문에
기존 BFS와 다른 로직이 필요합니다.
두 개의 구슬에 대한 위치를 관리해야 하므로
visited 배열은 4차원으로 선언해
두 구슬의 위치에 따른 방문 처리를 수행할 수 있도록 구현했습니다.
그래서 BFS를 수행할 객체를 생성했습니다.
Beads는 두 구슬의 좌표값과 이동 횟수를 저장합니다.
기울이기 로직
플래그의 역할
잘 안보일 수 있겠습니다만
redFlag blueFlag에 대한 내용입니다.
여기서 flag는 각각의 구슬이 구멍에 들어갔는지 여부를 판단하며
redFlag만 켜진 경우를 성공redFlagblueFlag둘 다 켜진 경우는 실패로 간주- 나머지의 경우는 성공도 실패도 아니기에 다음
BFS수행하도록
플래그를 사용해 3가지 경우로 나누었습니다.
카운트의 역할
다음은 rCount bCount에 대한 내용입니다.
여기서 count들은 각 색깔들이 기울였을 때 이동한 횟수를 나타내며
기울이려는 축에 같은 선상에 존재하는 경우
겹치는 게 되는데
이 때 rCount bCount 를 비교해
- 더 적게 움직인 구슬이 벽면과 가깝게,
- 더 많이 움직인 구슬이 그 옆에 위치할 수 있도록
겹치는 구슬을 분리하기 위한 역할입니다.
이동 로직
나머지는 BFS와 동일합니다.
기존 2차원에서 4차원으로 확장되기는 했지만 구조는 같습니다.
4방향으로 기울이는 로직을 수행하고
이동 후 두 구슬이 정확히 동일한 위치에 방문한 적이 있는지 방문 여부를 확인하고
- 방문한 적이 있다면 패스
- 방문한 적이 없다면, 로직에 의해
정답 반환실패다음 큐에 저장등을 수행합니다.
예제
다음과 같은 입력을 예제로 사용해보겠습니다.
입력
7 7
#######
#...RB#
#.#####
#.....#
#####.#
#O....#
#######초기 상태
초기에는 다음과 같이 존재하고 count는 0 입니다.
로직 수행
상하좌우 기울여보지만
왼쪽으로 기울이는 경우밖에 없고
왼쪽으로 기울이게 되면 count는 1
이 때 내부적으로는
redFlag와 blueFlag가 모두 false이므로
다음 BFS를 수행하기 위해 기울인 위치에 대해 방문 처리 큐에 저장
그리고 기울였을 때
벽면에 두 구슬이 동일한 좌표에 존재합니다.
그렇기 때문에
rCount bCount를 비교해 구슬이 겹쳐있지 않도록 분리하는 로직도 수행됩니다.
두 번째 기울이기 입니다.
상하좌우 모두 기울여보지만
아래로 밖에 갈 수 없습니다.
위와 왼쪽으로 기울이는 경우: 구슬 위치 변화 없음
오른쪽으로 기울이는 경우: 초기화 좌표와 동일함 (방문 처리된 곳)
아래로 기울이는 경우: 두 구슬의 새로운 위치 방문
이번에도 역시 두 플래그는 false
두 구슬이 겹치는 상태는 없습니다.
세 번째 기울이기 입니다.
오른쪽으로 가는 경우만이 새로운 경우가 됩니다.
이번에도 역시 두 플래그는 false
두 구슬이 겹치는 상태는 없습니다.
네 번째 기울이기 입니다.
아래로 가는 경우만이 새로운 경우가 됩니다.
이번에도 역시 두 플래그는 false
두 구슬이 겹치는 상태는 없습니다.
다섯 번째 기울이기 입니다.
왼쪽으로 가는 경우만이 새로운 경우가 됩니다.
이번에는 redFlag는 true, blueFlag는 false가 됩니다.
이 경우 해당 문제의 조건에 충족하므로 1을 반환하고 로직이 종료됩니다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.StringTokenizer;
// 빨간 구슬과 파란 구슬의 위치 및 이동 횟수를 저장하는 클래스
class Beads {
int ry, rx; // 빨간 구슬의 위치
int by, bx; // 파란 구슬의 위치
int count; // 이동 횟수
public Beads() {}
public Beads(int ry, int rx, int by, int bx, int count) {
this.ry = ry;
this.rx = rx;
this.by = by;
this.bx = bx;
this.count = count;
}
}
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int[] dy = {-1, 1, 0, 0};
static int[] dx = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
// 보드의 크기 입력
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
char[][] board = new char[N][M]; // 게임 보드
boolean[][][][] visited = new boolean[N][M][N][M]; // 4차원 방문 배열: 각 구슬의 좌표 조합을 기록
Beads beads = new Beads(); // 초기 구슬 상태
beads.count = 0;
int ex = 0, ey = 0; // 구멍(O)의 좌표
// 보드 정보 및 구슬, 구멍 위치 파싱
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < M; j++) {
char c = s.charAt(j);
if (c == 'B') {
beads.by = i;
beads.bx = j;
} else if (c == 'R') {
beads.ry = i;
beads.rx = j;
} else if (c == 'O') {
ey = i;
ex = j;
}
board[i][j] = c;
}
}
System.out.println(bfs(board, visited, ey, ex, beads));
}
static int bfs(char[][] board, boolean[][][][] visited, int ey, int ex, Beads init) {
ArrayDeque<Beads> q = new ArrayDeque<>();
q.offer(init);
visited[init.ry][init.rx][init.by][init.bx] = true;
while (!q.isEmpty()) {
Beads beads = q.poll();
// 10번 초과로 움직이면 실패
if (beads.count == 10) return 0;
// 4방향으로 구슬을 굴려보기
for (int d = 0; d < 4; d++) {
int nry = beads.ry;
int nrx = beads.rx;
int nby = beads.by;
int nbx = beads.bx;
boolean redFlag = false;
boolean blueFlag = false;
int rCount = 0;
int bCount = 0;
// 빨간 구슬 이동
while (board[nry + dy[d]][nrx + dx[d]] != '#') {
nry += dy[d];
nrx += dx[d];
rCount++;
if (nry == ey && nrx == ex) {
redFlag = true;
break;
}
}
// 파란 구슬 이동
while (board[nby + dy[d]][nbx + dx[d]] != '#') {
nby += dy[d];
nbx += dx[d];
bCount++;
if (nby == ey && nbx == ex) {
blueFlag = true;
break;
}
}
// 파란 구슬이 빠졌으면 실패
if (blueFlag) continue;
// 빨간 구슬만 빠졌으면 성공
if (redFlag) return 1;
// 두 구슬이 같은 위치에 도달했을 경우, 더 많이 이동한 구슬을 한 칸 뒤로
if (nry == nby && nrx == nbx) {
if (rCount > bCount) {
nry -= dy[d];
nrx -= dx[d];
} else {
nby -= dy[d];
nbx -= dx[d];
}
}
// 아직 방문하지 않은 상태면 큐에 추가
if (!visited[nry][nrx][nby][nbx]) {
visited[nry][nrx][nby][nbx] = true;
q.offer(new Beads(nry, nrx, nby, nbx, beads.count + 1));
}
}
}
// 10번 이내에 성공하지 못하면 0 반환
return 0;
}
}