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

문제

 

분석

그래프로 풀면 될것 같다.

인접행렬로 풀어 봤다.

그래프를 단순히 2차 배열로 만들었다

간선이 없으면 처음 가본길이므로 값을 증가한다.

간선이 있다면 이미 지나간 길이므로 값을 증가하지 않는다.,

 

이렇게 보면 쉽지만... 구현한 코드가 좀 복잡 했다

아직 실력이 많이 부족한것 같다.

 

완전탐색 + 그래프 인접행렬 이렇게 풀면 될것 같다.

 

구현

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

int nodeVal[2000][2000];
int graphMap[2000][2000];

int substitution(int x, int y){
    return  nodeVal[x][y];   
}

int solution(string dirs) {
    int answer = 0;
    int cnt = 1;
    for(int i = 0; i <= 10; i ++){
        for(int j = 0; j <= 10; j++){
            nodeVal[i][j] = cnt++;
        }
    }
 
    int x = 5 , y = 5 ;
    for(int i = 0; i < dirs.size(); i++){
        if( dirs.at(i) == 'U' ){
            if( y+1 <= 10 ){
                int curPoint = substitution(x,y+1);
                int nextPoint = substitution(x,y);
                y++;
                if(graphMap[curPoint][nextPoint] != 1){
                    answer++;
                    graphMap[curPoint][nextPoint] = 1;
                    graphMap[nextPoint][curPoint] = 1;
                } 
            }
        } else if( dirs.at(i) == 'L' ) {
            if( x-1 >= 0 ){
                int curPoint = substitution(x-1,y);
                int nextPoint = substitution(x,y);
                x--;
                if(graphMap[curPoint][nextPoint] != 1){
                    answer++;
                    graphMap[curPoint][nextPoint] = 1;
                    graphMap[nextPoint][curPoint] = 1;
                } 
            }
        } else if ( dirs.at(i) == 'R' ) {
            if( x+1 <= 10 ){
                int curPoint = substitution(x+1,y);
                int nextPoint = substitution(x,y);
                x++;
                if(graphMap[curPoint][nextPoint] != 1){
                    answer++;
                    graphMap[curPoint][nextPoint] = 1;
                    graphMap[nextPoint][curPoint] = 1;
                } 
            }
        } else if( dirs.at(i) == 'D' ) {
            if( y-1 >= 0 ){
                int curPoint = substitution(x,y-1);
                int nextPoint = substitution(x,y);
                y--;
                if(graphMap[curPoint][nextPoint] != 1){
                    answer++;
                    graphMap[curPoint][nextPoint] = 1;
                    graphMap[nextPoint][curPoint] = 1;
                } 
            }
        }
    }
    
    return answer;
}

 

 

 

 

문제링크: https://programmers.co.kr/learn/courses/30/lessons/49994

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