프로그래머스. 카드 짝 맞추기

https://programmers.co.kr/learn/courses/30/lessons/72415

코딩테스트 연습 - 카드 짝 맞추기

 

문제의 핵심은 

1) 어느 프렌즈부터 짝을 맞출것인지 정하는것과 

2) 카드를 찾으러 이동하는데 한칸씩 가는 방법 뿐만 아니라 컨트롤 키를 이용해 보드의 끝 혹은 다른 카드까지 한번에 도달할수 있기 때문에 하나의 카드에서 다른 하나의 카드로 이동하는데 걸리는 최소 행동수를 구하는 것이다. 

 

1)번은 프렌즈의 수가 최대 6명이기 때문에 next_permutation 함수로 모든 순열을 구하면된다. 

예를들어 1,2,3 프렌즈가 있다면 

1,2,3 : 1번 프렌즈의 짝을 맞추고, 2번 프렌즈의 짝을 맞추고, 3번 프렌즈의 짝을 맞춘다

2,1,3

2,3,1 

...

이런식으로 모든 경우를 다 계산해보면 된다.

 

2)번이 개인적으로 어려웠는데 그냥 한칸씩 이동하는 것이라면 일반적인 bfs 알고리즘이면 되지만 

컨트롤 키를 이용해서 보드의 끝까지 혹은 다른 카드까지 한번에 도달할수 있기 때문에 이 부분이 까다로웠다.

이 부분은 bfs 에서 한칸씩 이동하는 것 외에, 현재 칸에서 하나의 방향으로 보드의 끝까지 도달하거나 카드를 만날때까지 이동해보면 된다.

따라서 다음과 같이 

// 한칸씩 이동
for(int j = 0; j < 4; j++)
{
    int nr = r + dr[j];
    int nc = c + dc[j];
    if(nr < 0 || nr >= 4 || nc < 0 || nc >= 4) continue;
    if(mark[nr][nc]) continue;
    mark[nr][nc] = true;
    q.push({{nr,nc}, depth+1});
}

// 컨트롤키를 이용한 이동
// 4방향으로 보드의 끝 or 카드를 만날때까지 이동
for(int j = 0; j < 4; j++)
{
    int nr = r + dr[j];
    int nc = c + dc[j];
    while(true)
    {
        // 보드의 끝 도달
        if(nr < 0 || nr >= 4 || nc < 0 || nc >= 4)
        {
            nr -= dr[j];
            nc -= dc[j];
            break;
        }
        if(_board[nr][nc] != 0) break;
        nr += dr[j];
        nc += dc[j];
    }
    if(!mark[nr][nc])
    {
        mark[nr][nc] = true;
        q.push({{nr,nc}, depth+1});
    }
}

현재 칸에서 한칸씩 이동하는 경우를 큐에 푸쉬.

현재 칸에서 특정 방향으로 보드의 끝까지 or 카드를 만날때까지 이동한 경우를 푸쉬해주면 된다.

 

 

 

 

---

2022.02.04

다시 풀어봤는데 또 틀린 부분이 있었다.

컨트롤 키를 이용해서 이동하는 부분이었다.

컨트롤 키를 이용해서 이동했을때 보드의 끝이나 카드가 있는 지점을 만나면

해당 지점의 방문여부를 확인하고 방문하지 않았으면 무조건 큐에 푸쉬하도록 했는데

이 부분에서 카드가 있는 지점이 이미 방문한 지점이면 무시되고 보드의 끝까지 이동되도록  코드를 잘못작성했다.

해당 부분을 고쳐주니 통과했다.