[Programmers] 방문 길이 (C++)

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

왜 간선 좌표로 파악해야하는지 이해하기

 

Try 1 실패 이유

1. 한 방향으로만 흔적을 남김 -> 한 방향으로 이동 시 역 방향으로 돌아왔을 때도 자취를 남겨야함

2. 배열을 생성했을 때, 배열의 각 요소의 초기값은 0이 아니라 dump값 임

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(string dis) 
{
    int answer = 0;

    vector<vector<int>> w;
    for(int i=0; i<11; i++)
    {
        vector<int> v = {0,0,0,0,0,0,0,0,0,0,0};
        w.push_back(v);
    }
    
    int x = 5;
    int y = 5;
    w[y][x] = 1;
    
    for(int i=0; i<dis.size(); i++)
    {
        if(dis[i] == 'U' && y>=1)
            y--;
        else if(dis[i] == 'D' && y<=9)
            y++;
        else if(dis[i] == 'R' && x<=9)
            x++;
        else if(dis[i] == 'L' && x>=1)
            x--;
        else
        {
            w[y][x] = 0;
            answer--;
        }

        
        cout << x << " " << y << endl;
        
        
        answer++;
        if(w[y][x] == 1)
            break;
        w[y][x] = 1;
    }
    return answer;
}

 

Try 2 성공

#include <string>
#include <iostream>

using namespace std;

int solution(string dis) 
{
    int answer = 0;
    int map[11][11][11][11];
    
        
    int x = 5, y = 5;
    

    for(int i=0; i<dis.size(); i++)
    {   
        
      if(dis[i] == 'U' && y>=1)
      {
          if(map[y][x][y-1][x] !=1)
          {
            map[y-1][x][y][x] = 1;
            map[y][x][y-1][x] = 1;
            answer++;
          }
            y--;
      }
          
      else if(dis[i] == 'D' && y<=9)
      {
          if(map[y][x][y+1][x] != 1)
          {
            map[y][x][y+1][x] = 1;
            map[y+1][x][y][x] = 1;
            answer++;
          }
            y++;
      }
      else if(dis[i] == 'R' && x<=9)
      {
          if(map[y][x][y][x+1] != 1)
          {
            map[y][x][y][x+1] = 1;
            map[y][x+1][y][x] = 1; 
            answer++;
          }
          x++;
      }
      else if(dis[i] == 'L' && x>=1)
      {
         if(map[y][x][y][x-1] != 1)
         {
            map[y][x][y][x-1] = 1;
            map[y][x-1][y][x] = 1;
            answer++; 
         }
         x--;
      }
        
        cout << answer << endl;
        
    }
    
    return answer;
}