[C#/Programmers] Lv2. 방문 길이
Lv2 문제이다.
Winter Coding 에서 테스트로 나왔던 기출문제이다.
문제가 좀 길다.
생각 해 보기
문제는 길긴 하지만 생각보다는 별거 없다.
우선, 좌표계가 한정되어 있고, 이미 갔던 길을 중복해서 체크하지 않아야 하기 때문에 별도로 체크를 해 주는 자료구조를 하나 만들어야 함을 생각해야 한다.
나는 이차원 배열 두 개를 만들어 주었다.
왜 두개를 만들었냐 하면 좌표계의 한 점에서 갈 수 있는 것이 상, 하, 좌, 우의 네 가지 길이 있다. 상/하를 한 세트로 해서 갔던 길을 저장하는 배열 하나, 좌/우를 한 세트로 해서 갔던 길을 저장하는 배열을 하나 만들어 주었다.
즉, 위 그림과 같이 좌표에서 오른쪽길을 통과했는지 여부를 담는 Right 배열, 위쪽 길을 통과했는지 여부를 담는 Up배열 두 개를 만들어 주면 된다.
방향은 오른쪽, 위쪽만 만들어 두어 일관성을 가지게 하였다.
코드(C#)
using System;
public class Solution {
public int solution(string dirs) {
int answer = 0;
int x = 0;
int y = 0;
bool[,] upArr = new bool[11,10];
bool[,] rightArr = new bool[10,11];
foreach(char i in dirs){
switch(i){
case 'U':
if(y >= 5)
break;
if(upArr[x+5,y+5]== true){
y++;
break;
}
else{
upArr[x+5,y+5] = true;
y++;
answer++;
}
break;
case 'D':
if(y <= -5)
break;
y--;
if(upArr[x+5,y+5] == true)
break;
else{
upArr[x+5,y+5] = true;
answer++;
}
break;
case 'R':
if(x >= 5)
break;
if(rightArr[x+5,y+5] == true){
x++;
break;
}
else{
rightArr[x+5,y+5] = true;
x++;
answer++;
}
break;
case 'L':
if(x <= -5)
break;
x--;
if(rightArr[x+5,y+5] == true){
break;
}
else{
rightArr[x+5,y+5] = true;
answer++;
}
break;
}
}
return answer;
}
}여기서 좌표를 나타내는 x,y는 좌표숫자를 그대로 사용하였지만 배열index에서는 +5를 더해 주어 사용하였다.
그리고 위 그림과 같이 right 배열은 가로 10, 세로 11의 크기로 만들었으며, up은 그 반대인 11x10의 크기로 제작하였다.
그리고 한 번 지나간 길은 배열의 원소를 true로 바꾸어 주었으며, 이미 true일 경우에는 다음 바퀴를 돌게끔 하였다.
위 배열들은 해당 좌표에서 오른쪽, 위쪽 방향으로의 길을 체크하는 것이다. 즉, ‘L’(과 ‘D’)의 경우에는 한 칸을 먼저 좌측(아래쪽)으로 옮긴 다음에 옮긴 지점에서 오른쪽(위쪽)으로 이동하는 길이 true가 되어 있는가 확인 해 준다.
실수했던 부분
‘U’(와 ‘R’) 부분에서 이미 길이 true가 되어 있을 때 길 체크만 하고 y(x)좌표를 더하지 않고 바로 break;를 건 부분이었다.
“LRLR” 이렇게 한 길을 반복하는 경우에 ‘L’로 왼쪽으로 간 다음에 ‘R’이 들어왔을 때, 길 체크만 하고 다시 오른쪽으로 이동하지 못하여서 ‘L’이 다시 들어오게 되면 왼쪽 칸으로 한 번 더 이동하게 된 것 같은 효과가 나게 되어 answer이 예기치 못하게 늘어나게 되었다..
따라서 ‘R’(, ‘U’)의 경우에서 이미 지나 간 길일 때 x(y)좌표를 break; 전에 늘려주는 작업을 해 주니 의도했던 대로 작동하였다.