문제
https://softeer.ai/practice/info.do?idx=1&eid=577
요약
로봇은 명령어로 동작한다
- A 는 2번 앞으로 이동
- R 은 오르쪽으로 돌기
- L 은 왼쪽으로 돌기
로봇이 정해진 경로로 이동해야하는 이동하는 최소의 명령어 길이를 구하는거다.
로봇이 출발할수 있는 지점과 방향은 지정되지 않고 우리가 출력해야한다.
제약조건
-
5 ≤ H, W ≤ 25
-
사수는 한 번 이상의 A 명령을 내렸다. 따라서, 로봇이 방문한 칸 수는 최소 3개 이상이다.
-
이 문제의 경우 목표를 달성할 수 있는 방안이 여러개 일 수 있으며 그 중 아무 것이나 출력해도 답으로 처리된다.
Java 1초 1024MB
풀이
로봇이 할수 있는 경우의 수는 세가지다
- 앞으로 가기
- 왼쪽으로 돌기
- 오른쪽으로 돌기
이세가지 경우를 모두 탐방하되 갈수 없으면 재귀를 가지 않는 가지치기를 진행한다.
모든 칸 H W 에 대해 가능 한지 확인해야하기 때문에
O(H W 3 ^ H W) = O(3 ^ H * W)
이지만 중간에 못가는곳은 dfs 재귀를 안태우는 가지치기를 해서 더 빠르게 나올수 있다.
메모리의 경우 완탐시 복제되는 check 가 보통 문제 인데 O(HW)로 조건을 충족할수 있다.
시간 메모리는 해결되었고,dfs 를 활용한 완전탐색 알고리즘으로 작성했다.
코드는 앞서 말한 dfs 재귀로 가능한 앞, 왼쪽, 오른쪽 탐색하고 경우의 수마다 check 를 넘겨줘 경우의 수별로 독립적인 진행을 했다.
코드
package softeer.robotPath;
import java.util.*;
import java.io.*;
public class Main {
static int W;
static int H;
static boolean[][] map; // 시작 지점용
static boolean[][] OriginCheck; // 초기 입력 check
static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};// 위 오 아 왼 오른쪽 회전 기준
static String result = ""; // 결과 로 전달할 문자열
static int minSize = Integer.MAX_VALUE; // 명령어 길이 최소정보
static int[] resultCordi = new int[3]; // 결과 좌표 + 방향 담을 배열
public static void main(String args[]) throws IOException {
// 입력 받기, 초기화
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
H = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
map = new boolean[H][W];
OriginCheck = new boolean[H][W];
for (int row = 0; row < H; row++) {
String[] rowLine = br.readLine().split("");
for (int col = 0; col < W; col++) {
String value = rowLine[col];
if (value.equals("#")) {
map[row][col] = false;
OriginCheck[row][col] = false;
} else {
map[row][col] = true;
OriginCheck[row][col] = true;
}
}
}
// dfs
for (int row = 0; row < H; row++) {
for (int col = 0; col < W; col++) {
if (!map[row][col]) {//모든 점을 확인하다 시작이 가능한 map 이면 시작해라
for (int way = 0; way < 4; way++) {
int[] resCordi = new int[3]; // 결과 출력을위해 재귀 매개변수로 넘길 좌표 + 방향
resCordi[0] = row;
resCordi[1] = col;
resCordi[2] = way;
boolean[][] nextCheck = checkCopy(OriginCheck); // 복제
nextCheck[row][col] = true;
dfs(row, col, way, nextCheck, "", resCordi);
}
}
}
}
// 결과 출력 부분
System.out.println((resultCordi[0] + 1) + " " + (resultCordi[1] + 1));
if (resultCordi[2] == 0) { // 결과 매핑
System.out.println("^");
} else if (resultCordi[2] == 1) {
System.out.println(">");
} else if (resultCordi[2] == 2) {
System.out.println("v");
} else if (resultCordi[2] == 3) {
System.out.println("<");
}
System.out.println(result);
}
public static void dfs(int row, int col, int way, boolean[][] beforeCheck, String res, int[] resCordi) {
if (isAllTrue(beforeCheck) && res.length() < minSize) {
// 길이가 최소이고 전부 방문하면 종료하고 결과 전용 전역 변수에 넣는다.
minSize = res.length();
result = res;
resultCordi = resCordi.clone();
return;
}
// 전방이동
boolean[][] nextCheck = checkCopy(beforeCheck);
int[] d = dir[way];
int forwardR = row + d[0];//전방으로 이동
int forwardC = col + d[1];
if (isIn(forwardR, forwardC) && !nextCheck[forwardR][forwardC]) {// 한칸앞이 가능하면 앞으로 2칸 앞으로 시도
// A 명령어는 두번 이동한다 한번더 이동 + 체크
nextCheck[forwardR][forwardC] = true;
forwardR += d[0];
forwardC += d[1];
if (isIn(forwardR, forwardC) && !nextCheck[forwardR][forwardC]) {
nextCheck[forwardR][forwardC] = true;// 한번더 가능하면 이동
} else {// 불가능한 경우 다시 뒤로이동
forwardR -= d[0];
forwardC -= d[1];
}
dfs(forwardR, forwardC, way, nextCheck, res + "A", resCordi);
}
// 오른쪽 이동
nextCheck = checkCopy(beforeCheck);
int nextR = (way + 1) % 4; // 오른쪽 방향 회전
int[] rWay = dir[nextR];
int nextRrow = row + rWay[0];
int nextRcol = col + rWay[1];
if (isIn(nextRrow, nextRcol) && !nextCheck[nextRrow][nextRcol]) {
nextCheck[nextRrow][nextRcol] = true;
dfs(nextRrow, nextRcol, nextR, nextCheck, res + "R", resCordi);// 가능하면 재귀로 넘겨라
}
// 왼쪽이동
nextCheck = checkCopy(beforeCheck);
int nextL;
if (way == 0) { // 왼쪽 으로 회전 하드코딩말고 좀더 쉬운 방법이 있을텐데
nextL = 3;
} else if (way == 1) {
nextL = 0;
} else if (way == 2) {
nextL = 1;
} else {
nextL = 2;
}
int[] lWay = dir[nextL];
int nextLRow = row + lWay[0];// 왼쪽 방향으로 이동
int nextLCol = col + lWay[1];
if (isIn(nextLRow, nextLCol) && !nextCheck[nextLRow][nextLCol]) {
nextCheck[nextLRow][nextLCol] = true;
dfs(nextLRow, nextLCol, nextL, nextCheck, res + "L", resCordi);// 가능하면 재귀로 넘겨라
}
}
// 결과 확인할때 방문다해야 결과를 보여줄수 있다 모두 방분 했는지 체크하는 함수
public static boolean isAllTrue(boolean[][] checkTarget) {
for (boolean[] rowTarget : checkTarget) {
for (boolean b : rowTarget) {
if (!b) {
return false;
}
}
}
return true;
}
public static boolean[][] checkCopy(boolean[][] inCheck) {
boolean[][] re = new boolean[H][W];
for (int row = 0; row < H; row++) {
for (int col = 0; col < W; col++) {
re[row][col] = inCheck[row][col];
}
}
return re;
}
public static boolean isIn(int row, int col) {
return row >= 0 && row < H && col >= 0 && col < W;
}
}
알고리즘, SpringBoot, Java, DataBase