[프로그래머스] Summer/Winder coding 방문 길이 level2

문제 :

programmers.co.kr/learn/courses/30/lessons/49994

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

 

분석 :

처음에 dfs문제인줄 알고 마침 오늘 dfs 스터디 해서 dfs 짜다가 stack에 push 해줄 필요가 없음을 느끼고 

단순 문자열 길이만큼 for문을 돌아 answer 값을 증가 해주는 식으로 간소화 하였다.

 

1. 첫 접근 방식

갔던 간선은 또 갈 수 없으니 2차원 visit 배열 생성 후 false인 좌표에 대해서만 answer 값 증가시키기 

하지만 이 방식은 1번시, 도착 노드로 방문했던 (5,6)번지를 7번 작업 수행시 (5,6)번이 이미 방문한 노드가 되었으므로 7번 간선을 만들수 없게 된다. 그래서 정점 방식으로 접근하면 안된다는 것을 깨닫고 깊은 고뇌에 빠졌다 ... 

 

2. 두번째 접근 방식 

아 그러면 이전 방문 노드를 방문하고 다음 노드는 이미 방문된 상태임에도 7번 노드를 위해 다시 갈 수 있게 추가해주자 !

하지만 이 역시 

갔던 9번, 8번 간선은 포함하지 않아야 하는데 위 추가한 조건에 의해 포함되게 된다 😩으 .. 그러면 어쩌라구 ...

 

3번째 접근 방식

정점 기반이 아니라 간선 방식이 필요할거 같다는 생각이 들었다. 

이 전 노드를 저장하되 위 그림처럼 전에도 갔고 이번에도 간 노드가 true인 경우만 배제하고 넣어주면 되겠다 싶었다. 자세한 내용은 코드로 👉🏻👉🏻

시작 노드와 도착 노드를 pair 로 묶어 key 값으로 만들었고 이를 bool 값을 가지는 edge map을 하나 만들었다. 그리고 false일때에 대해 true로 간 표시를 해주었다.

 

 

c++ 코드 :

//
//  W] 2018_gameLine.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/04/30.
//

#include <stdio.h>
#include <stack>
#include <iostream>
#include <string.h>
#include <map>

using namespace std;

string dirs[3] = {"ULURRDLLU", "LRLRL", "LULLLLLLU" };


void make_line_dfs(){
    int cnt = 0;
    map<pair<pair<int, int>, pair<int, int>>, bool> edge;
    
    int dx = 5;
    int dy = 5;
    
    for(int i = 0; i < dirs[0].length(); i++){
       int priorX = dx;
       int priorY = dy;
       switch (dirs[0][i]) {
           case 'U':
               if( dy + 1 > 10){
                   continue;
               }
               dy += 1;
               break;
           case 'D':
                if(dy - 1 < 0){
                   continue;
               }
               dy -= 1;
              
               break;
           case 'R':
               if(dx + 1 > 10){
                   continue;
               }
               dx += 1;
               break;
           case 'L':
               if(dx - 1 < 0){
                   continue;
               }
               dx -= 1;
               break;
           default:
               break;
        }
        
        //if(dx < 0 || dy < 0 || dx >= 10 || dy >= 10) continue; // 걸어주니 false가 떴다 왜일까 ㅠ
        if(edge[make_pair(make_pair(priorX, priorY), make_pair(dx, dy))] == true) continue;
        
        //false 이면
        edge[make_pair(make_pair(priorX, priorY), make_pair(dx, dy))] = true;
        edge[make_pair(make_pair(dx, dy), make_pair(priorX, priorY))] = true;
        cnt++;
       

        
    }
    cout << "cnt : " << cnt << '\n';
        
    }
    
    
    
    

int main(){
    make_line_dfs();

    
    int answer = 0;
    
    return 0;
}

 

 

결과 :