[프로그래머스] 49994. 방문 길이 (C++)

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

문제 설명

1. 처음 지나는 거리의 길이 구하기

2. 방문했던 곳 또 방문할 수는 있지만, 이미 지나왔던 거리를 통해서 방문했다면 길이에 추가 X

 

풀이

1. -5 ~ 5 대신 0 ~ 10으로 좌표 설정

2. 좌표를 이동하기에 편리하도록 L, R, U, D을 각 0, 1, 2, 3으로 바꿈 (dx, dy 배열 사용하기 위해)

3. visit 배열에 이 좌표에서 이동한 방향 정보를 담음 (비트마스크 이용 -> 각 1, 2, 4, 8)

4. & 연산 -> 해당 방향으로 이동했었는지 확인 -> 이미 이동했었으면 길이에 더해주지 않고 이동만 함

5. 방향이 아니라 길을 방문했었는지 확인하는 것이 목표이므로 visit 배열의 도착 좌표의 이동 방향 정보도 추가해줘야 함!

ex. a -> b (left) 이동했으면 b -> a (right) 도 체크해줘야 함 

번거롭다고요 ? 그냥 전 이렇게 했어요 .. 

테케 8부터는 계속 실패 뜨더니 5번 고려 안 해서 그런 거였음 ㄱㅜ 짜증 

 

코드

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

int visit[11][11];
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1}; 

int solution(string dirs) {
    int answer = 0;
    int sy = 5, sx = 5;
    for(int i=0; i<dirs.length(); i++) {
        int dir = -1;
        if(dirs[i] == 'L') dir = 2;
        else if(dirs[i] == 'R') dir = 3;
        else if(dirs[i] == 'U') dir = 0;
        else dir = 1;
        int ay = sy + dy[dir];
        int ax = sx + dx[dir];
        if(ay < 0 || ay > 10 || ax < 0 || ax > 10) continue;
        if(visit[sy][sx] & int(pow(2, dir))) {
            sy = ay; sx = ax;
            continue;
        }
        visit[sy][sx] = visit[sy][sx] | int(pow(2, dir));
        if(dir % 2) visit[ay][ax] |= int(pow(2, dir-1));
        else visit[ay][ax] |= int(pow(2, dir+1));
        sy = ay; sx = ax;
        answer++;
        
    }
    return answer;
}