문제
https://softeer.ai/practice/info.do?idx=1&eid=577
요약
로봇은 명령어로 동작한다
A 는 2번 앞으로 이동
R 은 오르쪽으로 돌기
L 은 왼쪽으로 돌기
로봇이 정해진 경로로 이동해야하는 이동하는 최소의 명령어 길이를 구하는거다.
로봇이 출발할수 있는 지점과 방향은 지정되지 않고 우리가 출력해야한다.
제약조건
5 ≤ H, W ≤ 25
사수는 한 번 이상의 A 명령을 내렸다. 따라서, 로봇이 방문한 칸 수는 최소 3개 이상이다.
이 문제의 경우 목표를 달성할 수 있는 방안이 여러개 일 수 있으며 그 중 아무 것이나 출력해도 답으로 처리된다.
Java 1초 1024MB
풀이
로봇이 할수 있는 경우의 수는 세가지다
- 앞으로 가기
- 왼쪽으로 돌기
- 오른쪽으로 돌기
이세가지 경우를 모두 탐방하되 갈수 없으면 재귀를 가지 않는 dfs 를 진행한다.
개선점
- 모든 칸에대해 출발가능성을 보는것 -> 출발지점을 찾고 그 지점만 탐색하는방방법 추가 findStart() 함수로 구현
- 하드 코딩 되있던 왼쪽 회전 수학으로 변경
int nextL = ((way - 1) + 4) % 4;
코드
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
int[] startArr = findStart();
String temp = "";
originCheck[startArr[0]][startArr[1]] = true;
dfs(startArr[0], startArr[1], startArr[2], originCheck, temp);
// 결과 출력 부분
System.out.println((startArr[0] + 1) + " " + (startArr[1] + 1));
if (startArr[2] == 0) { // 결과 매핑
System.out.println("^");
} else if (startArr[2] == 1) {
System.out.println(">");
} else if (startArr[2] == 2) {
System.out.println("v");
} else if (startArr[2] == 3) {
System.out.println("<");
}
System.out.println(result);
}
public static int[] findStart(){
int minCount = Integer.MAX_VALUE;
int [] res = new int[3];
for(int row = 0; row < H; row++){
for(int col = 0; col < W; col++){
// 주변에 칸이 제일 작은게 출발점이다!
int neighborCount = 0;
int resWay = -1;
for(int way = 0; way < 4; way++){
int nextR = row + dir[way][0];
int nextC = col + dir[way][1];
if(!map[row][col] &&isIn(nextR, nextC) && !map[nextR][nextC]){
neighborCount+=1;
resWay = way;
}
}
if(minCount > neighborCount && neighborCount > 0){
minCount = neighborCount;
res[0] = row;
res[1] = col;
res[2] = resWay;
}
}
}
return res;
}
public static void dfs(int row, int col, int way, boolean[][] beforeCheck, String res) {
if (isAllTrue(beforeCheck) && res.length() < minSize) {
// 길이가 최소이고 전부 방문하면 종료하고 결과 전용 전역 변수에 넣는다.
minSize = res.length();
result = res;
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");
}
// 오른쪽 이동
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");// 가능하면 재귀로 넘겨라
}
// 왼쪽이동
nextCheck = checkCopy(beforeCheck);
int nextL = ((way - 1) + 4) %4;
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");// 가능하면 재귀로 넘겨라
}
}
// 결과 확인할때 방문다해야 결과를 보여줄수 있다 모두 방분 했는지 체크하는 함수
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