프로그래머스 Level 2 : 방문 길이 C언어

▶문제 : 코딩테스트 연습 - 방문 길이 | 프로그래머스 (programmers.co.kr)

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

 

▶코드 작성(아래에 개선 코드)

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int area[11][11][4]; //[4] = [위,아래,오른,왼] -> m,m1으로 나타냄

int solution(const char *dirs) {
    int x = 5, y = 5, m;   //이동한 x,y축과 방향 m
    int x1 = 5, y1 = 5, m1;//이동하기전의 x1,y1축과 방향 m
    int n = 0;             //처음으로 건너간 횟수

    for (int i = 0; dirs[i] != '\0'; i++) {//dirs문자열이 끝날 때까지 반복
        switch (dirs[i])
        {
        case 'U':
            if (y < 10) y++;//위로 한칸 이동
            m = 1;          //이동한 블록 - 위로 이동했으므로 연결지점은 아래로 표시
            m1 = 0;         //이동하기전 블록 - 위로 이동했으므로 연결지점은 위로 표시
            break;
        case 'D':
            if (y > 0) y--;//아래로 한칸 이동
            m = 0;         //이동한 블록 - 아래로 이동했으므로 연결지점은 위로 표시
            m1 = 1;        //이동하기전 블록 - 아래로 이동했으므로 연결지점은 아래로 표시
            break;
        case 'R':
            if (x < 10) x++;//오른쪽으로 한칸 이동
            m = 3;          //이동한 블록 - 오른쪽으로 이동했으므로 연결지점은 왼쪽으로 표시
            m1 = 2;         //이동하기전 블록 - 오른쪽으로 이동했으므로 연결지점은 오른쪽으로 표시
            break;
        case 'L':
            if (x > 0) x--;//왼쪽으로 한칸 이동
            m = 2;         //이동한 블록 - 왼쪽으로 이동했으므로 연결지점은 오른쪽으로 표시
            m1 = 3;        //이동하기전 블록 - 왼쪽으로 이동했으므로 연결지점은 왼쪽으로 표시
            break;
        }

        if (area[y1][x1][m1] == 0) {  //이동한적이 없을 때
            if (x != x1 || y != y1) { //움직임의 범위를 넘지 않았을 때
                area[y1][x1][m1] = 1; //이동한 방향으로 1 대입
                area[y][x][m] = 1;    //이동했던 방향으로 1 대입
                n++;
            }
        }

        x1 = x;//다음 이동을 위해 이동한 값 대입
        y1 = y;
    }

    return n;
}

더욱 코드를 깔끔하게 다듬을 수 있을 것이라 생각해 switch문에서 if문으로 바꿔준 후 정리하였다.

 

▶개선 코드

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int area[11][11][4]; //[4] = [위,아래,오른,왼] -> m,m1으로 나타냄

int solution(const char *dirs) {
    int x = 5, y = 5, m;   //이동한 x,y축과 방향 m
    int x1 = 5, y1 = 5, m1;//이동하기전의 x1,y1축과 방향 m
    int n = 0;             //처음으로 건너간 횟수

    for (int i = 0; dirs[i] != '\0'; i++) {//dirs문자열이 끝날 때까지 반복
        char s = dirs[i];
        if (s == 'U' && y < 10) {
            y++;   //위로 한칸 이동
            m = 1; //이동한 블록 - 위로 이동했으므로 연결지점은 아래로 표시
            m1 = 0;//이동하기전 블록 - 위로 이동했으므로 연결지점은 위로 표시
        }
        else if (s == 'D' && y > 0) {
            y--;   //아래로 한칸 이동
            m = 0; //이동한 블록 - 아래로 이동했으므로 연결지점은 위로 표시
            m1 = 1;//이동하기전 블록 - 아래로 이동했으므로 연결지점은 아래로 표시
        }
        else if (s == 'R' && x < 10) {
            x++;   //오른쪽으로 한칸 이동
            m = 3; //이동한 블록 - 오른쪽으로 이동했으므로 연결지점은 왼쪽으로 표시
            m1 = 2;//이동하기전 블록 - 오른쪽으로 이동했으므로 연결지점은 오른쪽으로 표시
        }
        else if (s == 'L' && x > 0) {
            x--;   //왼쪽으로 한칸 이동
            m = 2; //이동한 블록 - 왼쪽으로 이동했으므로 연결지점은 오른쪽으로 표시
            m1 = 3;//이동하기전 블록 - 왼쪽으로 이동했으므로 연결지점은 왼쪽으로 표시
        }
        else continue;//범위를 넘는다면 무시

        if (area[y1][x1][m1] == 0) {//m1의 방향으로 처음 움직인다면
            area[y1][x1][m1] = 1;//m1의 방향으로 움직임을 표시
            area[y][x][m] = 1;   //m의 방향에서 왔다는 표시
            n++;                 //처음으로 건너간 횟수
        }

        x1 = x;//다음 이동을 위해 이동한 값 대입
        y1 = y;
    }

    return n;
}

 

▶해석

문제를 보면 움직인 칸과 어디로 움직였는지 방향을 고려해 풀어야겠다고 생각했다.

이동 범위를 보면 0부터 10까지이고, 선을 이동하므로 [11][11] 크기의 2차원 배열을 선언해주었다.

여기서 4가지의 방향이 존재하고, 각 칸마다 필요하다고 생각하여 area [11][11][4] 배열을 선언하였다.

[4]는 각각 [위쪽 - 0 , 아래쪽 - 1 , 오른쪽 - 2 , 왼쪽 - 3]을 가리키고 그 값이 1이면 이동한 적이 있다는 표시이다.

 

변수를 보면 x, y는 이동한 좌표, m은 이동한 좌표에서 이동하기 전의 좌표를 바라보는 방향이다(이유는 아래에서 설명)

x1, y1는 이동하기전의 좌표이고, m1은 이동한 방향이다.

시작 지점은 5로 맞추어 중앙에서 시작하였다.

만약 처음에 'U' 위로 한 칸 이동한다면 y++해주어 다음과 같이 표현할 수 있다.

	x , y (5 , 6)
	x1 , y1 (5 , 5)

x1, y1 좌표의 기준으로 보면 위로 이동했으므로 [4]에서 위쪽은 0이므로 m1 = 0; 을 대입해준다.

x, y 좌표의 기준으로 보면 아래에서 위로 올라왔으므로 [4]에서 아래쪽은 1이므로 m = 1; 을 대입해준다.

그렇게 해서 각각 area [y1][x1][m1] = 1;   area [y][x][m] = 1; 이렇게 대입하여 이동한 선을 표시한다.

그러면 x, y 좌표에서 다시 'D' 아래로 한 칸 이동하려 해도 area [y=6][x=5][m=1] 값이 1이므로 이동하지 못한다.

이렇듯 이동한 블록끼리 서로의 방향을 가리키도록 하여 지나갔다는 표시를 하였다.

 

이동했다면 x1에 x를 y1에 y를 대입하여 다음 이동을 준비한다.