Life Engineering
[BOJ 13460] 구슬 탈출2 (Java) 본문
https://www.acmicpc.net/problem/13460
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 Main_BOJ_13460 {
static class Pos{
int red_r, red_c, blue_r, blue_c, dist;
Pos(int red_r, int red_c, int blue_r, int blue_c, int dist) {
this.red_r = red_r;
this.red_c = red_c;
this.blue_r = blue_r;
this.blue_c = blue_c;
this.dist=dist;
}
}
static char[][] map;
static int N, M;
static boolean[][][][] visited;
static int[] dr= {-1,1,0,0};
static int[] dc= {0,0,-1,1};
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
N=Integer.parseInt(st.nextToken());
M=Integer.parseInt(st.nextToken());
map=new char[N][M];
visited=new boolean[N][M][N][M];
int red_r=-1, red_c=-1, blue_r=-1, blue_c=-1;
for (int i=0; i<N; i++) {
String s=br.readLine();
for (int j=0; j<M; j++) {
map[i][j]=s.charAt(j);
if (map[i][j]=='B') {
blue_r=i;
blue_c=j;
}
else if (map[i][j]=='R') {
red_r=i;
red_c=j;
}
}
}
System.out.println(bfs(new Pos(red_r, red_c, blue_r, blue_c, 0)));
}
private static int bfs(Pos pos) {
Queue<Pos> q=new LinkedList<>();
q.add(pos);
visited[pos.red_r][pos.red_c][pos.blue_r][pos.blue_c]=true;
while (!q.isEmpty()) {
Pos p=q.poll();
if (p.dist>10) break;
if (map[p.red_r][p.red_c]=='O') return p.dist;
for (int i=0; i<4; i++) {
int[] red=move(p.red_r, p.red_c, i);
int[] blue=move(p.blue_r, p.blue_c, i);
Pos next=adjust(red[0], red[1], blue[0], blue[1], i, p); //움직인 위치
if (map[next.blue_r][next.blue_c]!='O' && !visited[next.red_r][next.red_c][next.blue_r][next.blue_c]) {
q.add(new Pos(next.red_r, next.red_c, next.blue_r, next.blue_c, p.dist+1));
visited[next.red_r][next.red_c][next.blue_r][next.blue_c]=true;
}
}
}
return -1;
}
private static int[] move(int start_r, int start_c, int d) {
int[] loc=new int[2];
int r=start_r, c=start_c;
while (true) {
r+=dr[d];
c+=dc[d];
if (map[r][c]=='#') {
r-=dr[d];
c-=dc[d];
break;
}
if (map[r][c]=='O') {
break;
}
}
loc[0]=r; loc[1]=c;
return loc;
}
private static Pos adjust(int rr, int rc, int br, int bc, int d, Pos before) {
Pos curr=new Pos(rr, rc, br, bc, -1);
if (rr==br && rc==bc) { //같을 때는 조정시키기
if (map[rr][rc]=='O') return curr;
if (d==0) {
if (before.red_r<before.blue_r) {
curr.blue_r+=1;
}
else{
curr.red_r+=1;
}
}
else if (d==1) {
if (before.red_r<before.blue_r) {
curr.red_r-=1;
}
else {
curr.blue_r-=1;
}
}
else if (d==2) {
if (before.red_c<before.blue_c) {
curr.blue_c+=1;
}
else {
curr.red_c+=1;
}
}
else if (d==3) {
if (before.red_c<before.blue_c) {
curr.red_c-=1;
}
else {
curr.blue_c-=1;
}
}
}
return curr;
}
}
BFS 로 풀었다.
visited[빨간공 행][빨간공 열][파란공 행][파란공 열] 이런 식으로 방문 배열을 구현했다.
일단 빨간 공, 파란 공을 쭉 굴려준 뒤 만약 두 공의 위치가 같다면, hole 인 경우 그대로 리턴하고 그렇지 않은 경우 위치를 재조정해준다.
예를 들어, 직전에 R 00 B 이런 식으로 있었는데 왼쪽으로 굴린 경우라면, 파란 공 열의 위치를 +1 로 해서 재조정해주는 방식이다..
'Problem Solving' 카테고리의 다른 글
[프로그래머스] 주차 요금 계산 (Java) (0) | 2022.05.06 |
---|---|
[프로그래머스] 카드 짝 맞추기 (Java) (0) | 2022.05.05 |
[BOJ 19237] 어른 상어 (Java) (0) | 2022.04.27 |
[BOJ 23289] 온풍기 안녕! (Java) (0) | 2022.04.26 |
[BOJ 15684] 사다리 조작 (Java) (0) | 2022.04.23 |