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

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

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

프로그래머스

---

 

해결전략

 

방문 경로 길이 구하기

4차원 배열

 

---

 

처음 시도한 코드 - 테스트 케이스 5개 실패

 

#include <string>
#include <vector>
using namespace std;

int answer = 0;  // 방문 길이
int ch[11][11];  // (y, x) 방문 체크
int chDir[11][11][4]; 
int y = 0, x = 0; // 시작 위치

// 방문 체크 후 방문한 적이 없으면 길이 늘리기
void isVisited(char d, int y, int x) 
{
    if (ch[y + 5][x + 5] == 0) // 해당 좌표에 방문한적이 없으면
    {
        answer++; // 길이 늘리기
        ch[y + 5][x + 5] = 1; // 방문 체크
        return;
    }
    else if (ch[y + 5][x + 5] == 1) // 해당 좌표에 방문한적이 있다면
    {
        int tmp;
        if (d == 'U') tmp = 1;
        else if (d == 'D') tmp = 0;
        else if (d == 'R') tmp = 3;
        else if (d == 'L') tmp = 2;

        if(chDir[y + 5][x + 5][tmp] == 0) 
        {
            answer++;
            return;
        }
    }

    return;
}

void Move(char d, int& y, int& x)
{
    if (y < -5 || 5 < y || x < -5 || 5 < x) return;

    // 이동
    if (d == 'U'){
	    if(y < 5){
            chDir[y + 5][x + 5][0] = 1;
            y = y + 1;
            isVisited(d, y, x);
            chDir[y + 5][x + 5][1] = 1;
	    }
    }
    else if (d == 'D') {
        if (-5 < y) {
            chDir[y+5][x+5][1] = 1;
            y = y - 1;
            isVisited(d, y, x);
            chDir[y + 5][x + 5][0] = 1;
        }
    }
    else if (d == 'R') {
        if (x < 5) {
            chDir[y + 5][x + 5][2] = 1;
            x = x + 1;
            isVisited(d, y, x);
            chDir[y + 5][x + 5][3] = 1;
        }
    }
    else if (d == 'L') {
        if (-5 < x) {
            chDir[y + 5][x + 5][3] = 1;
            x = x - 1;
            isVisited(d, y, x);
            chDir[y + 5][x + 5][2] = 1;
        }
    }    
}

int solution(string dirs) {
    
    for(int i=0; i<dirs.size(); i++)
    {
        Move(dirs[i], y, x);
    }

    return answer;
}

 

이 코드에서는 방문한 경로를 체크하는 데 있어서 일부 문제가 있다. '방문 길이' 문제의 경우, 이전에 방문한 좌표가 아니라 특정 경로를 이전에 걸었는지 여부를 확인해야 한다. 즉, 어떤 좌표에서 다른 좌표로 가는 경로를 이미 걸었는지를 확인해야 하는데, 위의 코드에서는 단순히 좌표 자체의 방문 여부만을 체크하고 있다.

따라서 chDir 배열을 사용하여 각각의 위치에서 4개의 방향으로 가본 적이 있는지 기록하려는 시도는 하였으나, 현재 구현된 로직은 충분하지 않다. 각각의 위치와 그 위치에서 특정 방향으로 움직인 적이 있는지 (즉, 특정 '경로'를 이미 걸었는지) 기록해야 한다.

---

 

정답 코드

 

#include <iostream>
#include <string>
using namespace std;

int answer = 0;  // 방문 길이
int chPath[11][11][11][11]; // 4차원 배열로, 시작점과 끝점에 따른 경로의 방문 여부를 저장
int y = 0, x = 0;  // 현재 위치. 초기값은 (0, 0)

// 이전 위치에서 현재 위치까지의 경로가 처음 방문하는 경로인지 확인하고, 그렇다면 answer를 증가시키고 해당 경로를 방문했다고 표시
void checkPath(int prevY, int prevX, int y, int x) 
{
	if(chPath[prevY + 5][prevX + 5][y + 5][x + 5] == 0
        && chPath[y + 5][x + 5][prevY + 5][prevX + 5] == 0)
	{
        chPath[prevY + 5][prevX + 5][y + 5][x + 5] = 1;
        answer++;
        chPath[y + 5][x + 5][prevY + 5][prevX + 5] = 1;
	}

    return;
}

// 주어진 문자 d에 따라 U D R L 중 하나의 방향으로 이동. 이동 후 checkPath 함수 호출하여 해당 경로 체크
void Move(char d, int& y, int& x)
{
    int prevY = y;
    int prevX = x;

    // 이동
    if (d == 'U' && y < 5){
        y = y + 1;
        checkPath(prevY, prevX, y, x);
    }
    else if (d == 'D' && -5 < y) {
        y = y - 1;
        checkPath(prevY, prevX, y, x);
    }
    else if (d == 'R' && x < 5) {
        x = x + 1;
        checkPath(prevY, prevX, y, x);
    }
    else if (d == 'L' && -5 < x) {
        x = x - 1;
        checkPath(prevY, prevX, y, x);
    }    
}

int solution(string dirs) {
    
    for(int i=0; i<dirs.size(); i++)
    {
        Move(dirs[i], y, x);
    }

    return answer;
}

int main()
{
    string testcase1 = "ULURRDLLU";
    string testcase2 = "LULLLLLLU";

    cout << solution(testcase1);

    return 0;
}

 

 

 

 

---

 

 

더 쉬운 풀이

 

#include <string>
using namespace std;

int dy[4] = { 1, -1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };

bool visited[11][11][11][11]; // 방문 체크를 위한 배열. 현재 위치와 다음 위치 사이의 경로를 저장

int solution(string dirs) {
    int answer = 0; // 방문 길이
    int x = 5; // 시작 x 좌표
    int y = 5; // 시작 y 좌표

    for (char dir : dirs) // 입력받은 명령어들을 순회
    { 
        int idx; //idx는 dy와 dx의 인덱스로 사용
        switch (dir) { 
			case 'U':
				idx = 0;
				break;
			case 'D':
				idx = 1;
				break;
			case 'R':
				idx = 2;
				break;
			case 'L':
				idx = 3;
				break;
        }

        int ny = y + dy[idx]; // 다음 y 좌표 계산
        int nx = x + dx[idx]; // 다음 x 좌표 계산

        // 다음 좌표가 유효한 범위인지 확인 (좌표계는 -5 ~ +5 이지만 배열 인덱스로는 음수를 사용할 수 없으므로 모든 값에 +5 해서 0 ~ 10 범위로 변환)
        if (nx >= 0 && nx <= 10 && ny >= 0 && ny <= 10) 
        { 
            if (visited[x][y][nx][ny] == false) // 해당 경로를 처음 지나가는 경우인지 확인
            {         
                visited[x][y][nx][ny] = true;   // 해당 경로 방문 체크 
                visited[nx][ny][x][y] = true;   // 반대 방향 경로도 동시에 체크 (왕복경우도 고려)
                answer++;                       // 방문 길이 증가시킴
            }

            y = ny;
            x = nx;
        }

    }

    return answer;
}

 

 

 

 

---