[프로그래머스] 방문 길이 C++ 풀이 및 해설

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

프로그래머스

풀이 방법

현재 좌표와 다음 좌표를 가지고 있다면 이 두 좌표를 통해 걸어본적이 있는 길인지 확인이 가능합니다.

map을 통해 현재 좌표 x,y와 이동할 다음 좌표를 통해 걸어본적이 있는 길인지 확인합니다.

(현재 좌표에서 다음 좌표로 map에 등록되어있는지 확인) => 주의! 확인시 양방향으로 확인해야함

 

양방향: (x,y) => (nx,ny) 그리고 (nx,ny) => (x,y)

 

1. 만약 걸어본 적이 없는 길이라면 현재 좌표에서 다음 좌표로 가는 길을 등록합니다.

2. 걸어본적이 있는 길이라면 현재 좌표를 다음 좌표로 옮기고 다음 명령을 확인합니다.

 

 

전체 코드

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

int solution(string dirs) {
    int answer = 0;
    map<pair<pair<int,int>,pair<int,int>>, bool> m; // (현재위치, 다음위치), 방문여부
    int x,y,nx,ny; // 현재위치(x,y), 다음위치(nx,ny)
    x=0; y=0; nx=0; ny=0;
    for(int i=0; i<dirs.length(); i++) {
        
        // 조건문으로 명령어와 좌표평면 범위 검사
        if(dirs[i]=='U' && ny+1<=5) {
            ny++;
        } else if(dirs[i]=='D' && ny-1>=-5) {
            ny--;
        } else if(dirs[i]=='R' && nx+1<=5) {
            nx++;
        } else if(dirs[i]=='L' && nx-1>=-5) {
            nx--;
        } else { // 범위를 벗어나는 명령어라면 무시
            continue;
        }
        
        // 현재좌표와 다음좌표을 통해 걸어본 적 있는 길인지 검사
        if(m.find(make_pair(make_pair(x,y),make_pair(nx,ny)))==m.end() && 
           m.find(make_pair(make_pair(nx,ny),make_pair(x,y)))==m.end()) {
            m.insert({make_pair(make_pair(x,y),make_pair(nx,ny)), true}); // 현재좌표와 다음좌표 등록
            answer++;
        }
           x=nx; y=ny; // 현재좌표를 다음좌표로 갱신
    }
    
    return answer;
}