[Softeer]로봇이 지나간 경로

*알고리즘 문제를 풀면서 나의 감정과 의식의 흐름을 기록한 일기입니다. (제출한 코드에 대한 자세한 설명은 없음!)

 

나는 지금 매우 기쁘다ㅠㅠ

왜냐하면 당연히 틀리겠지.. 생각하면서 제출한 내 풀이가 정답으로 통과했기 떄문이다..ㅠㅠ 그것도 한번에!!

 

얼마나 어떻게 틀릴지 그거라도 확인하자라는 마음으로 제출했는데...

기쁘다ㅠㅠ

https://softeer.ai/practice/6275

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

이문제는 처음에 어떻게 접근하지.. 고민하면서 코드짜는데

점점 노가다 스러운 코딩이 되었다...

 

지나간길 체크해주고, 회전한 방향에 따라서 R인지 L 인지 붙여주고,

어랏 잘못갔네 하면 다시 원복해주고..

지나갔던 길 원복해주는걸 수월하게 하기 위해서 String을 사용하면서 String 길이를 먼저 구해놓고,

잘못갔으면 그 길이대로 다시 돌려놓고.. check true 했던것도 다시 false 로 해주고..

 

보통 로직을 간단하게 하지 않고

내가 생각하기에 좀 노가다스럽고 구구절절 로직을 짜면, 거의 틀려왔었기 때문에

이번에도 틀리겠지? 하면서 제출했는데 맞았당

 

근데 시간이 좀 많이 걸리긴 했다..

여유부리면서 푸니까 풀었지, 시험볼때 제한된 시간 안에 풀라고 했으면 내가 이걸 풀수잇었을까? 싶다.

 

더 간단하게 풀수있는 로직을 좀더 생각해봐야겠다.

 

import java.io.*;

public class Main {

    static int n;
    static int m;
    static char[][] a;
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};

    static boolean checkAllPassed(boolean[][] check){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(a[i][j] == '#' && !check[i][j]){
                    return false;
                }
            }
        }
        return true;
    }

    static String go(int x, int y, boolean[][] check, String ans, int prevDir){

        if(checkAllPassed(check)){
            return "S" + ans;
        }

        int ansLength = ans.length();
        for(int dir=prevDir; dir<prevDir+4; dir++){
            int k = dir%4;
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(nx<0 || nx>= n || ny<0 || ny>=m || a[nx][ny] == '.' || check[nx][ny]){
                continue;
            }
            check[nx][ny] = true;
            int nx2 = nx + dx[k];
            int ny2 = ny + dy[k];
            if(nx2<0 || nx2>= n || ny2<0 || ny2>=m){
                if(checkAllPassed(check)){
                    if(dir-prevDir == 1){
                        ans += "R";
                    }else if(dir-prevDir == 2){
                        ans += "R";
                        ans += "R";
                    }else if(dir-prevDir == 3){
                        ans += "L";
                    }
                    ans += "A";
                    return "S" + ans;
                }else{
                    check[nx][ny] = false;
                    continue;
                }
            }

            if(a[nx2][ny2]=='.' || check[nx2][ny2]){
                check[nx][ny] = false;
                continue;
            }

            check[nx2][ny2] = true;
            if(dir-prevDir == 1){
                ans += "R";
            }else if(dir-prevDir == 2){
                ans += "R";
                ans += "R";
            }else if(dir-prevDir == 3){
                ans += "L";
            }
            ans += "A";
            String temp = go(nx2, ny2, check, ans, k);
            if(temp.startsWith("S")){
                return temp;
            }

            check[nx][ny] = false;
            check[nx2][ny2] = false;
            ans = ans.substring(0, ansLength);
        }
        return ans;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] nm = br.readLine().split(" ");
        n = Integer.parseInt(nm[0]);
        m = Integer.parseInt(nm[1]);
        a = new char[n][m];
        for(int i=0; i<n; i++){
            a[i] = br.readLine().toCharArray();
        }

        int startX = -1;
        int startY = -1;
        char startDir = '^';
        String ans = null;
        OUTER:for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(a[i][j] == '#'){
                    boolean[][] check = new boolean[n][m];
                    check[i][j] = true;
                    ans = go(i, j, check, "", 0);
                    if(ans.startsWith("S")){
                        startX = i+1;
                        startY = j+1;
                        ans = ans.substring(1);
                        break OUTER;
                    }
                }
            }
        }
        if(ans.startsWith("L")){
            startDir = '<';
            ans = ans.substring(1);
        }else if(ans.startsWith("RR")){
            startDir = 'v';
            ans = ans.substring(2);
        }else if(ans.startsWith("R")){
            startDir = '>';
            ans = ans.substring(1);
        }
        bw.write(startX + " "  + startY + "\n");
        bw.write(startDir + "\n");
        bw.write(ans);
        bw.close();
    }

}