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

문제

문제 설명

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

U: 위쪽으로 한 칸 가기

D: 아래쪽으로 한 칸 가기

R: 오른쪽으로 한 칸 가기

L: 왼쪽으로 한 칸 가기

캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.

명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 return 하는 solution 함수를 완성해 주세요.

제한사항

dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.
dirs의 길이는 500 이하의 자연수입니다.

---

풀이 당시 떠올린 Idea

처음엔 Map<Key, Value>로 좌표(x,y)를 key 값, 상하좌우 방문 boolean배열을 value에 넣어서 해결하고자 했으나, Map의 get함수에 Object를 넣어야 해서 매번 Object를 만들거나 따로 Object를 관리해야해서 다른 방법 구상함.

boolean 배열 대신 이진값으로 상하좌우 이동한 적 있는지 확인
상하좌우를 비트 연산으로 체크

---

풀이 후 알게 된 Idea

---

코드 풀이

1. 좌표 평면을 (-5,-5) ~ (5,5) 에서 x,y를 5씩 더해 (0,0) ~ (10,10) 으로 가정 -> 배열 편하게 사용하려고

2. 상하좌우 방향을 각각 비트연산하기 위해서 이진법으로 상($1000_2$ = 8), 하($0100_2 = 4$), 좌($0010_2 = 2$), 우($0001_2 = 1$)로 가정

3. visitedDir[x][y]=(상하좌우 값) -> (x,y) 좌표에서 상하좌우 중 이동한 방향 저장 -> &, | 비트연산하려고
   i. 해당 방향으로 이동할 수 있는지 확인
   ii-a. visitedDir[xpos][ypox] & up -> & 비트연산으로 해당 방향으로 간 적이 있는지 확인
   ii-b. 간 적 있으면 해당 방향으로 좌표만 이동
   ii-c. 간 적 없으면 | 비트연산 한 값 대입, 이동한 좌표에서도 반대 방향으로 대입, answer 증가

---

작성한 코드

class Solution {
    public int solution(String dirs) {
		int answer = 0;
		int[][] visitedDir = new int[11][11];

		// 좌표 -5 ~ 5 를 0 ~ 10 으로 가정
		int xpos = 5;
		int ypos = 5;

		// Up(1000) Down(0100) Left(0010) Right(0001)
		int up = 8;
		int down = 4;
		int left = 2;
		int right = 1;

		for (int i = 0; i < dirs.length(); i++) {
			char direction = dirs.charAt(i);
			switch (direction) {
			case 'U':
				if (ypos == 10)
					break;

				if ((visitedDir[xpos][ypos] & up) == up) {
					ypos++;
					break;
				}

				visitedDir[xpos][ypos] |= up;
				visitedDir[xpos][++ypos] |= down;

				answer++;

				break;

			case 'D':
				if (ypos == 0)
					break;

				if ((visitedDir[xpos][ypos] & down) == down) {
					ypos--;
					break;
				}

				visitedDir[xpos][ypos] |= down;
				visitedDir[xpos][--ypos] |= up;

				answer++;

				break;

			case 'L':
				if (xpos == 0)
					break;

				if ((visitedDir[xpos][ypos] & left) == left) {
					xpos--;
					break;
				}

				visitedDir[xpos][ypos] |= left;
				visitedDir[--xpos][ypos] |= right;

				answer++;

				break;

			case 'R':
				if (xpos == 10)
					break;

				if ((visitedDir[xpos][ypos] & right) == right) {
					xpos++;
					break;
				}

				visitedDir[xpos][ypos] |= right;
				visitedDir[++xpos][ypos] |= left;

				answer++;

				break;
			}
		}

		return answer;
	}
}