전형적인 시간은 오래잡아먹고 맞춰도 테케만 맞춘거같은 느낌의 문제...
무조건 또 풀어봐야한다.
난이도 Lv1 라고 하지만 Lv2 이상인 것 같다.
문제
입출력
문제해석
다음과 같은 숫자 다이얼에서 각각 왼손/오른손 엄지로 누르는 최적의 위치 탐색(BFS)
실패코드
우선 풀면서도 너무 헷갈리게 품... 흐름을 놓치면 첨부터 보느라 시간너무 잡아먹음
너무 알고리즘 보단 하드코딩 느낌으로 품 (시간소모 심하고, 효율성 떨어짐)
간과한점
해당문제는 번호판의 배열이 총 12개로 한정적이기때문에 번호판의 좌표를 배열에 넣어야한다.
또한 바둑판 최단거리등이 나올때 dfs/bfs으로 접근하려는 선입견X
(x,y) -> (a,b) 지점 사이의 거리의 로직을 생각
#include <string>
#include <queue>
#include <iostream>
using namespace std;
int cal[] = { -3, +1, +3, -1 };//위, 오, 아, 왼
int locLeft = 10;
int locRight= 12;
string solution(vector<int> numbers, string hand)
{
string answer = "";
for (int i = 0; i < numbers.size(); i++)
{
if (numbers[i] == 0)
numbers[i] = 11;
if (numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7)
{
locLeft = numbers[i];
answer += "L";
}
else if (numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9)
{
locRight = numbers[i];
answer += "R";
}
//numbers[i] == 0 이면 11이다.
else
{
int cntL = 1;
int cntR = 1;
int comL;
int comR;
bool visit[12] = { false, };
bool visit2[12] = { false, };
queue<int> q;
queue<int> q2;
q.push(locRight);
q2.push(locLeft);
while (!q.empty())
{
int ex =0;
int x = q.front();
visit[x] = true;
q.pop();
for (int w = 0; w < 4; w++)
{
int dx = x + cal[w];
if (visit[dx] == true)
continue;
//예외처리 1) 1,4,7,11 왼쪽불가 2)1,2,3 위로불가 , (3) 3,6,9,12 오불가 , (4) 10,11,12아래로 불가
if (w == 1 && (dx == 4 || dx == 7 || dx == 10 || dx == 13))
continue;
if (w == 0 && (dx == 0 || dx == 1))//위로
continue;
//아래
if (w == 2 && dx == 14 || dx == 15)
continue;
if (dx == 1 || dx == 4 || dx + cal[w] == 7)
continue;
q.push(dx);
visit[dx] = true;
if (dx == numbers[i])
{
ex = 1;
comR = cntR+1;
break;
}
}
if (ex == 1)
{
break;
}
cntR++;
}
while (!q2.empty())
{
int ex=0;
int x = q2.front();
visit2[x] = true;
q2.pop();
for (int w = 0; w < 4; w++)
{
int dx = x + cal[w];
if (visit2[dx] == true)
continue;
//예외처리 1) 1,4,7,11 왼쪽불가 2)1,2,3 위로불가 , (3) 3,6,9,12 오불가 , (4) 10,11,12아래로 불가
if (w == 3 && (dx == 0 || dx == 3 || dx == 6 || dx == 9))
continue;
if (w == 0 && (dx == -2 || dx == -1))//위로
continue;
if (w == 2 && dx == 13 || dx == 14)
continue;
if (dx == 3 || dx == 6 || dx == 9)
continue;
q2.push(dx);
visit2[dx] = true;
if (dx== numbers[i])
{
comL = cntL+1;
ex = 1;
break;
}
}
if (ex == 1)
{
break;
}
cntL++;
}
if (comL < comR)
{
answer += "L";
locLeft = numbers[i];
}
else if (comL > comR)
{
answer += "R";
locRight = numbers[i];
}
else
{
if (hand == "right")
{
answer += "R";
locRight = numbers[i];
}
else
{
answer += "L";
locLeft = numbers[i];
}
}
}
}
return answer;
}
Sol 코드
우선 현지점 목표지점까지 거리는 (x,y) -> (a,b) 절대값(x-a) + (y-n) 이다.
우선 각 번호의 좌표배열을 만들고 목표지점과의 거리를 구하는 로직을 구현함.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int locLeft = 10;
int locRight = 11;
pair<int, int> ar[12] = { { 3, 1 }, { 0, 0 }, { 0, 1 }, { 0, 2 }, { 1, 0 }, { 1, 1 }, { 1, 2 }, { 2, 0 }, { 2, 1 }, { 2, 2 }, { 3, 0 }, { 3, 2 } };
string solution(vector<int> numbers, string hand)
{
//solution({ 7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2 }, "left");
string answer = "";
for (int i = 0; i < numbers.size(); i++)
{
if (numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7)
{
locLeft = numbers[i];
answer += "L";
}
else if (numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9)
{
locRight = numbers[i];
answer += "R";
}
//numbers[i] == 0 이면 11이다.
else
{
int leftmax = abs(ar[numbers[i]].first - ar[locLeft].first) + abs(ar[numbers[i]].second - ar[locLeft].second);
int rightmax = abs(ar[numbers[i]].first - ar[locRight].first) + abs(ar[numbers[i]].second - ar[locRight].second);
if (leftmax > rightmax)
{
locRight = numbers[i];
answer += "R";
}
else if (leftmax < rightmax)
{
locLeft = numbers[i];
answer += "L";
}
else if (leftmax == rightmax)
{
if (hand == "right")
{
locRight = numbers[i];
answer += "R";
}
else
{
locLeft = numbers[i];
answer += "L";
}
}
}
}
return answer;
}
int main()
{
//solution({ 1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5 }, "right");
solution({ 7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2 }, "left");
return 0;
}
