백준_통나무 옮기기_1938[Java]
2019. 4. 19. 16:49ㆍ알고리즘문제/백준
문제
https://www.acmicpc.net/problem/1938
풀이
앞서 풀었던 로봇 문제와 풀이 방법이 매우 유사하지만 조건이 조금 까다롭다.
BFS로 풀이하되 회전이 이동과 같은 타이밍에 할 수 있도록 조건을 준다.
* 주의할 점
통나무가 목표지점에 절대 도달하지 못하는 경우가 있다. 이때 0을 출력해야 한다.
- TEST CASE
input :
4
BBB1
1111
1111
1EEE
output : 0
그 외 샘플테스트는 다른 분들이 올려주신것을 참고해보자 ! 링크
코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N;
static char[][] map;
static boolean[][][] visit;
static final int VERTICAL = 0;
static final int HORIZON = 1;
static Logs start, end;
static class Logs {
int x;
int y;
int dir;
int cnt;
Logs(int x, int y, int dir, int cnt) {
this.x = x;
this.y = y;
this.dir = dir;
this.cnt = cnt;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
sc.nextLine();
map = new char[50][50];
visit = new boolean[50][50][2];
start = new Logs(-1, -1, -1, 0);
end = new Logs(-1, -1, -1, 0);
int sCnt = 1;
int eCnt = 1;
for (int i = 0; i < N; i++) {
String s = sc.nextLine();
for (int j = 0; j < N; j++) {
map[i][j] = s.charAt(j);
if (map[i][j] == 'B') {
if (sCnt == 1) {
start.x = j;
start.y = i;
sCnt++;
} else if (sCnt == 2) {
if (start.x == j)
start.dir = VERTICAL;
else
start.dir = HORIZON;
start.x = j;
start.y = i;
sCnt++;
}
}
if (map[i][j] == 'E') {
if (eCnt == 1) {
end.x = j;
end.y = i;
eCnt++;
} else if (eCnt == 2) {
if (end.x == j)
end.dir = VERTICAL;
else
end.dir = HORIZON;
end.x = j;
end.y = i;
eCnt++;
}
}
}
}
//System.out.println(start.x + " , " + start.y + " , " + start.dir);
//System.out.println(end.x + " , " + end.y + " , " + end.dir);
dfs();
visit[start.y][start.x][start.dir] = true;
sc.close();
}
static int[] dx = { 0, 0, -1, 1, 0 };
static int[] dy = { -1, 1, 0, 0, 0 };
private static void dfs() {
Queue<Logs> q = new LinkedList<Logs>();
q.add(new Logs(start.x, start.y, start.dir, 0));
while (!q.isEmpty()) {
Logs curLog = q.poll();
int curX = curLog.x;
int curY = curLog.y;
int curDir = curLog.dir;
int cnt = curLog.cnt;
// 기저사례 추가해야한다.
if(curX == end.x && curY == end.y && curDir == end.dir) {
System.out.println(cnt);
return;
}
for (int i = 1; i <= 5; i++) {
int nextX = curX + dx[i-1];
int nextY = curY + dy[i-1];
if (nextX < N && nextY < N && nextX >= 0 && nextY >= 0) {
switch (i) {
case 1: // UP
if ((curDir == 0 && nextY > 0 && map[nextY-1][nextX] != '1') // 수직
|| (curDir == 1 && map[nextY][nextX-1] != '1' && map[nextY][nextX] != '1' && map[nextY][nextX+1] != '1')) { // 수평
if(!visit[nextY][nextX][curDir]) {
visit[nextY][nextX][curDir] = true;
q.add(new Logs(nextX, nextY, curDir, cnt+1));
}
}else {
break;
}
break;
case 2: // DOWN
if ((curDir == 0 && nextY < N-1 && map[nextY+1][nextX] != '1') // 수직
|| (curDir == 1 && map[nextY][nextX-1] != '1' && map[nextY][nextX] != '1' && map[nextY][nextX+1] != '1')) { // 수평
if(!visit[nextY][nextX][curDir]) {
visit[nextY][nextX][curDir] = true;
q.add(new Logs(nextX, nextY, curDir, cnt+1));
}
}else {
break;
}
break;
case 3: // LEFT
if ((curDir == 0 && map[nextY-1][nextX] != '1' && map[nextY][nextX] != '1' && map[nextY+1][nextX] != '1') // 수직
|| (curDir == 1 && nextX-1 >= 0 && map[nextY][nextX-1] != '1' )) { // 수평
if(!visit[nextY][nextX][curDir]) {
visit[nextY][nextX][curDir] = true;
q.add(new Logs(nextX, nextY, curDir, cnt+1));
}
}else {
break;
}
break;
case 4: // RIGHT
if ((curDir == 0 && map[nextY-1][nextX] != '1' && map[nextY][nextX] != '1' && map[nextY+1][nextX] != '1') // 수직
|| (curDir == 1 && nextX+1 < N && map[nextY][nextX+1] != '1' )) { // 수평
if(!visit[nextY][nextX][curDir]) {
visit[nextY][nextX][curDir] = true;
q.add(new Logs(nextX, nextY, curDir, cnt+1));
}
}else {
break;
}
break;
case 5:
if (curX != 0 && curX != N - 1 && curY != 0 && curY != N - 1) {
if (curDir == 0) { // 수직
if (curDir == 0 && map[curY][curX - 1] != '1' && map[curY - 1][curX - 1] != '1' && map[curY + 1][curX - 1] != '1'
&& map[curY][curX + 1] != '1' && map[curY - 1][curX + 1] != '1'
&& map[curY + 1][curX + 1] != '1') {
curDir = 1;
if(!visit[nextY][nextX][curDir]) {
visit[nextY][nextX][curDir] = true;
q.add(new Logs(nextX, nextY, curDir, cnt+1));
}
} else {
break;
}
} else { // 수평
if (map[curY - 1][curX - 1] != '1' && map[curY - 1][curX] != '1' && map[curY - 1][curX + 1] != '1'
&& map[curY + 1][curX - 1] != '1' && map[curY + 1][curX] != '1'
&& map[curY + 1][curX + 1] != '1') {
curDir = 0;
if(!visit[nextY][nextX][curDir]) {
visit[nextY][nextX][curDir] = true;
q.add(new Logs(nextX, nextY, curDir, cnt+1));
}
} else {
break;
}
}
}
break;
}
}
}
}
System.out.println("0");
return;
}
}
참고
- 내 블로그만 참고했다 ㅎㅎㅎㅎ뿌듯 !
https://heedipro.tistory.com/256
'알고리즘문제 > 백준' 카테고리의 다른 글
백준_포도주마시기_2156[Java] (0) | 2019.04.24 |
---|---|
백준_말이 되고픈 원숭이_1600[Java] (0) | 2019.04.22 |
백준_안전영역_2468[Java] (0) | 2019.04.19 |
백준_로봇_1726[Java] (0) | 2019.04.19 |
백준_달이 차오른다, 가자._1194[Java] (0) | 2019.04.12 |