C++ / 프로그래머스 / 방문 길이

문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/49994

프로그래머스

 

 

문제풀이

 

좌표는 (-5, -5)부터 (5, 5)까지 11*11의 크기를 갖는다.

캐릭터는 (0, 0)의 위치에서 시작하고 4가지 명령어에 따라 움직이며, 좌표 평면을 벗어날 수 없다.

배열에 인덱스는 음수가 될 수 없으므로 (0, 0)부터 (10, 10)까지, 캐릭터는 (5, 5)의 위치에 있다고 두고 문제를 풀었다.

 

bool isEnd(int y, int x) {
    if (y < 0 || y>10 || x < 0 || x>10) return false;
    else return true;
}

캐릭터가 좌표평면을 벗어났는지 판별하는 함수이다.

y, x가 0 이하, 10 초과 라면 false를 return 하고 그 외의 경우는 true를 return 한다.

 

 

void isVisit(int y, int x, char dir) {
    if (dir == 'U') {
        if (visited[y][x][0] == false) {
            visited[y][x][0] = true;
            visited[y + 1][x][1] = true;
            ++answer;
        }
    }
    else if (dir == 'D') {
        if (visited[y][x][1] == false) {
            visited[y][x][1] = true;
            visited[y - 1][x][0] = true;
            ++answer;
        }
    }
    else if (dir == 'L') {
        if (visited[y][x][2] == false) {
            visited[y][x][2] = true;
            visited[y][x + 1][3] = true;
            ++answer;
        }
    }
    else if (dir == 'R') {
        if (visited[y][x][3] == false) {
            visited[y][x][3] = true;
            visited[y][x - 1][2] = true;
            ++answer;
        }
    }
}

이동할 다음 칸이 방문한 적이 있는지를 판별하는 함수이다.

해당 좌표에 도착했을 때 상, 하, 좌, 우, 어느 방향에서 왔는지를 표시하기 위해 2차원 배열이 아닌 3차원 방문 배열을 사용했다.

하지만 문제에서는 (0, 0)에서 (0, 1)을 가나 (0, 1)에서 (0, 0)을 가나 같은 길이므로 한 길을 방문했으면 두 인덱스를 true로 바꿔준다.

U인 경우는 아래에서 위로 왔으므로 다음 칸 [0]을 true로 바꾼다.

이는 위에서 아래로 간 길과 같은 길 임으로 visited [y + 1][x][1] 값도 true로 바꾼다.

나머지 네 방향도 위와 마찬가지로 바꾸면 된다.

 

    for (int idx = 0; idx < dirs.size(); ++idx) {
        if (dirs[idx] == 'U') {
            if (isEnd(y - 1, x) == false) continue;
            else y -= 1;
        }
        else if (dirs[idx] == 'D') {
            if (isEnd(y + 1, x) == false) continue;
            else y += 1;
        }
        else if (dirs[idx] == 'L') {
            if (isEnd(y, x - 1) == false) continue;
            else x -= 1;
        }
        else if (dirs[idx] == 'R') {
            if (isEnd(y, x + 1) == false) continue;
            else x += 1;
        }
        isVisit(y, x, dirs[idx]);
    }

명령어를 탐색하면서 U, D, L, R 상황에 맞게 조건문을 통해 다음 칸이 밖을 벗어났는지를 확인한다.

벗어났다면 다음 명령어로 넘어간다.

벗어나지 않았다면 y, x값을 다음칸으로 갱신해 준다.

그다음 해당 칸이 방문했는지를 isVisit함수를 통해 판별하고 방문한 적이 없으면 함수를 통해 answer가 +1 된다.

 

 

코드

#include <string>
#include <vector>
#define pii pair<int, int>
using namespace std;

int visited[11][11][4];
int answer;

bool isEnd(int y, int x) {
    if (y < 0 || y>10 || x < 0 || x>10) return false;
    else return true;
}

void isVisit(int y, int x, char dir) {
    if (dir == 'U') {
        if (visited[y][x][0] == false) {
            visited[y][x][0] = true;
            visited[y + 1][x][1] = true;
            ++answer;
        }
    }
    else if (dir == 'D') {
        if (visited[y][x][1] == false) {
            visited[y][x][1] = true;
            visited[y - 1][x][0] = true;
            ++answer;
        }
    }
    else if (dir == 'L') {
        if (visited[y][x][2] == false) {
            visited[y][x][2] = true;
            visited[y][x + 1][3] = true;
            ++answer;
        }
    }
    else if (dir == 'R') {
        if (visited[y][x][3] == false) {
            visited[y][x][3] = true;
            visited[y][x - 1][2] = true;
            ++answer;
        }
    }
}

int solution(string dirs) {
    int y(5), x(5);

    for (int idx = 0; idx < dirs.size(); ++idx) {
        if (dirs[idx] == 'U') {
            if (isEnd(y - 1, x) == false) continue;
            else y -= 1;
        }
        else if (dirs[idx] == 'D') {
            if (isEnd(y + 1, x) == false) continue;
            else y += 1;
        }
        else if (dirs[idx] == 'L') {
            if (isEnd(y, x - 1) == false) continue;
            else x -= 1;
        }
        else if (dirs[idx] == 'R') {
            if (isEnd(y, x + 1) == false) continue;
            else x += 1;
        }
        isVisit(y, x, dirs[idx]);
    }

    return answer;
}