[알고리즘] 프로그래머스 방문 길이 -Summer/Winter Coding(~2018)- (선을 방문하는 문제)

https://programmers.co.kr/learn/courses/30/lessons/49994?language=java

코딩테스트 연습 - 방문 길이

 

 

 

프로그래머스 LEVEL3 의 방문 길이 문제를 풀어봤습니다 ㅎㅎ

처음에 별생각없이 좌표를 칸으로 취급하고 바로 2차원 배열의 map, isVIsisted 하고 bfs queue 로 접근해서 풀었는데 한문제만 맞고 나머지 한문제는 틀리고 오답이 나왔었습니다.

바로 위와 같이 7번처럼 방문이 안되야하는데 된걸로 되서 잘못풀었단거를 꺠달았습니다.

 

그래서 어디서 어디로 왔는지 알아야했습니다. 이를 4차원 배열을 이용해서 풀었습니다. 1,2 차원 지점에서 3,4차원지점으로 이동했다는 것을 기록합니다.

문제 풀이방법이 더 간단해졌습니다. 

 

풀이는 다음과 같습니다.

 

[Java]

class Solution {
    private static int answer = 0;
    private static boolean[][][][] isVisited = new boolean[11][11][11][11]; // (x,y) -> (x,y) 로 이동한 적 있는지
    private static int x, y; //현재좌표
    private static int x2, y2; //이동할좌표
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, -1, 0, 1};

    public int solution(String dirs) {
        x = 5;
        y = 5;
        x2 = 5;
        y2 = 5;
        for (char move : dirs.toCharArray()) {
            x = x2;
            y = y2;
            if (move == 'L') { //좌하우상
                x2 = x + dx[0];
                y2 = y + dy[0];
            } else if (move == 'D') {
                x2 = x + dx[1];
                y2 = y + dy[1];
            } else if (move == 'R') {
                x2 = x + dx[2];
                y2 = y + dy[2];
            } else {
                x2 = x + dx[3];
                y2 = y + dy[3];
            }

            //범위벗어난거처리
            if (x2 < 0 || x2 > 10 || y2 < 0 || y2 > 10) {
                //이동하기 전 좌표로 바꿔줌
                x2 = x;
                y2 = y;
                continue;
            }

            //이동가능한 좌표, 첫방문이면 답 +1
            if (!isVisited[x][y][x2][y2]) {
                isVisited[x][y][x2][y2] = true;
                isVisited[x2][y2][x][y] = true;
                answer++;
            }
        }

        return answer;
    }
}

 

 

 

[kotlin]

internal class Solution {

    fun solution(dirs: String): Int {
        var answer = 0
        val isVisited = Array(11) { Array(11) { Array(11) { BooleanArray(11) } } } // (x,y) -> (x,y) 로 이동한 적 있는지
        var x: Int = 5 //현재좌표
        var y: Int = 5
        var x2: Int = 5 //이동할좌표
        var y2: Int = 5
        val dx = intArrayOf(-1, 0, 1, 0)
        val dy = intArrayOf(0, -1, 0, 1)
        for (move in dirs.toCharArray()) {
            x = x2
            y = y2
            when (move) {
                'L' -> { //좌하우상
                    x2 = x + dx[0]
                    y2 = y + dy[0]
                }
                'D' -> {
                    x2 = x + dx[1]
                    y2 = y + dy[1]
                }
                'R' -> {
                    x2 = x + dx[2]
                    y2 = y + dy[2]
                }
                else -> {
                    x2 = x + dx[3]
                    y2 = y + dy[3]
                }
            }

            //범위벗어난거처리
            if (x2 < 0 || x2 > 10 || y2 < 0 || y2 > 10) {
                //이동하기 전 좌표로 바꿔줌
                x2 = x
                y2 = y
                continue
            }

            //이동가능한 좌표, 첫방문이면 답 +1
            if (!isVisited[x][y][x2][y2]) {
                isVisited[x][y][x2][y2] = true
                isVisited[x2][y2][x][y] = true
                answer++
            }
        }

        return answer
    }
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다!!