6. 카드 짝 맞추기

BFS로 최소 조작 횟수를 구할 수 있다는 점, Ctrl+방향키를 눌렀을 때의 처리 방법, 재귀함수로 순열을 생성하는 방법

  1. 완전 탐색, 순열 : 숫자 카드마다 2장이 존재하는데 각 카드마다 어떤 것을 먼저 선택할지 2가지 경우의 수가 존재한다! 따라서 각 숫자카드마다 선택하는 순서를 정하는 순열을 생성한다! => 재귀함수로 구현. ex)1A-(1B)-2A-2B, 1A-(1B)-2B-2A, 1B-(1A)-2A-2B, 1B-(1A)-2B-2A

  2. 2차원 배열의 너비우선탐색(BFS) ⭐️⭐️⭐️⭐️⭐️ BFS의 개념을 정확하게 이해하고 있어야 한다. 지금까지는 1칸 이동하는 것이 "거리"1이라고 생각했다. 2차원 배열에서 1칸 이동하는 것과 "거리" 개념의 값과 동일하게 매치되었다. 이 문제에서는 (0,0)->(1,0) : 1, (0,0)->(3,0) : 1 두가지 경우 모두 값이 1이다. 우리는 이 값을 "거리"가 아니라 "조작 횟수"라는 개념을 도입한다. 따라서, 기존의 동일한 "거리"값인 인접 노드들을 큐에 넣었다면, 이번에는 동일한 "조작 횟수"값인 인접 노드들을 큐에 넣는 것이다! 그러면 최소 "거리"를 구하는 방식으로 최소 "조작 횟수"를 구할 수 있게 된다. => 최소 조작 횟수. 1에서 구한 순열마다 최소 조작 횟수를 구한다. 방향키를 누르는 경우와 ctrl+방향키를 누르는 경우 모두 조작 횟수는 1번이다. ex) 백준 리모컨/말이 되고 싶은 원숭이 문제 출발점 : (0,0), 도착점 : (3,0)일 때, Ctrl+방향키 누른 경우 이동 좌표를 바로 정답으로 리턴하는 백트랙킹 식으로 가능하지 않을까 생각했는데, 위에서 언급한 것처럼 방향키/Ctrl+방향키 모두 거리(조작횟수)가 1이기 때문에 큐에 함께 들어가는 것이고, Ctrl+방향키로 이동하는 경우가 최단 거리(최소 조작 횟수)인 보장은 없다고 한다. Ctrl+방향키로 최솟값을 바로 찾아서 탐색을 종료해야할 것 같지만 이러한 이유로 각 노드마다 상하좌우 탐색하여 큐에서 꺼낸 좌표가 도착점 좌표일 경우 그 좌표의 거리값(=최소 조작 횟수)를 리턴한다. => "조작 횟수"가 동일한 칸들을 큐에 넣고, 큐에서 꺼낼 때 목적지 좌표인지 확인한다. 그때 목적지 좌표라면 그 좌표의 "조작 횟수" 값을 리턴하면 된다.

"한칸 이동하는 것과, Ctrl로 여러칸 이동하는 것이 조작 횟수가 동일하기 때문에 둘 다 넣어야 합니다. Ctrl로 이동하는 경로가 최단 경로라는 보장이 없습니다.

입력 크기도 작지만, 2차원 공간에서 최단 거리를 구해야 하는 문제에서는 BFS를 이용하는 경우가 많습니다. 문제 조건이 단순하면 다익스트라 알고리즘을 이용할 수도 있지만, 대부분은 부가적인 조건이 존재하고 이 조건들을 고려해서 다익스트라 알고리즘을 수행하기가 번거롭기 때문입니다."

구현. 시뮬레이션 - 재귀함수가 동작하는 방식

1A를 먼저 선택하는 경우, 1B로 시작하는 순열 생성(재귀함수 호출) 재귀함수 go(index=0)부터 go(index+1)과 유사한 모습. index번째 카드 순서를 정하고, 지금까지 선택한 조작횟수를 더해간다. one = bfs(src,1A) + bfs(1A,1B);//1A먼저 선택. Math.min(ret, one + go(1B));//1B로 시작하는 순열 생성. 재귀함수 호출 =>go(1B)는 1B에서 시작하여 num=2 순열 생성. one = bfs(src,2A) + bfs(2A,2B) //2A먼저 선택. Math.min(ret,one + go(2B));//2B로 시작하는 순열 생성. 재귀함수 호출

이런 식으로 각 재귀함수는 그 시점에서 조작 횟수를 선택하는 순서에 따라 one 또는 two에 저장한다.그리고 마지막 숫자의 순서까지 다 선택한 후에 ret=INF가 되어 호출된 역순으로 리턴되어 경우의 수의 최종 조작 횟수가 ret에 저장된다.

2번째로 풀었을 때 틀린 이유

  1. BFS - Ctrl + 방향키 반복문 : 현재의 방향(d)대로 범위 초과하지 않을 때까지 반복해서 이동한다. i-for문으로 반복문 구성. => 순서가 잘못됨. 현재 아래 코드에서는 이미 1칸 이동한 좌표(nx,ny)를 아무런 조건 검사 없이 바로 한번 더 이동시켜버리는데, (nx,ny) 칸이 숫자인지 검사하고, 범위 체크하는 것이 우선적으로 필요하다. =>범위 체크를 해야하는 좌표는 1칸 이동한 "현재"의 좌표 (nx,ny)가 아니라 1칸 더 이동할 (nx+dx[d],ny+dy[d]) 이다! => 범위를 초과하는 경우 바로 break;로 반복문을 탈출해야한다! 그렇지 않으면 그 다음 반복문 차례에서 Board[nx][nu]에 접근할 때 배열 초과 에러가 난다!!

    for(int i=0;i<2;i++){
    nx += dx[d];
    ny += dy[d];
    if(check(nx,ny)) continue;
    if(Board[nx][ny] != 0) break;
}
if(!visited[nx][ny]){
    visited[nx][ny] = true;
    q.add(new Point(nx,ny,cur.cnt+1));
}

    올바른 코드 : 범위초과를 제일먼저 하지 않아도 되는 이유는 이미 위에서 한칸 이동하면서 범위 체크를 해주었기 때문에 한번 필터링한 이후라 바로 범위체크하지 않고 Board값 먼저 검사해줘도 되는 것이다!

    1. for(int i=0;i<2;i++){//4x4크기이기 때문에 최돼 2번더 이동할 수 있음.
    //1. 한번 더 이동하기 전에 먼저 숫자 찾은 경우 검사!
    if(Board[nx][ny] != 0) break;//이동 반복을 종료. 숫자를 찾은 경우. 근데 이게 찾으려는 숫자가 맞나??
    //2. 범위 초과 검사!
    if(check(nx+dx[d],ny+dy[d])) break;
    //d와 동일한 방향으로 범위가 넘지 않을 때까지 계속 반복해서 이동한다!!!
    nx += dx[d];
    ny += dy[d];
}
if(!visited[nx][ny]){
    visited[nx][ny] = true;
    q.add(new Point(nx,ny,cur.cnt+1));
}

  2. 이해를 못했던 재귀함수 호출 부분 일단 2가지 포인트가 있다. 첫번째로, 재귀함수가 구현된 2개의 ret를 구하는 부분에서의 목표는 각각의 경우에 대한 비용을 구하고, 최종적으로 더 작은 값인 ret를 도출하는 것이다. 내가 생각했던 것은 "순열"을 구하는 것이였는데 여기서 중요한 포인트는 각각의 경우에 대한 "비용"을 구하는 것이다. 또한, "순열"에 포커스를 맞춘 것으로 인해 첫번째 ret를 한 후 원복하는 부분을 추가하면 스택오버플로우가 발생하는데 이 이유는 선택①,원복,선택②,원복 이렇게 되면 이미 one,two에서 선택을 했는데 선택한 것에 대해 다시 선택하는 것이 무의미할 뿐더러, num=6까지 갔을 때에 이미 num=6①에서 했던 연산들임에도 불구하고 원복하는 부분으로 인해 num=6②에서는 num=6①에서 했던 동작을 동일하게 수행하게 된다. num=5로 리턴되기는 하지만 결국 각 num에서 동일한 동작을 2번 수행하게 되고, 리턴 될때마다 모든 동작들이 다 2번씩 연산이 될 것이다. 중요한 것, 구해야하는 것은 단지 one, two에서 구한 각각의 경우에 대한 비용인데 말이다! num=1① [2① 3① 4① 5① 6 ① 6① 5① 6① 6① 4①5①5①6①6① 3①4①4①5①5①6①6① 2①3①3①4①4①5①5①6①6①] 1① [ ] one, two에서 이미 순서와 비용을 구했다. 각각의 경우, 재귀함수 호출해서 최종 비용을 구하면 되는 것이다! 이 논리로 다시 코드를 살펴보면 num=1일 때, one, two에서 one = 1A1B비용, two = 1B1A비용을 저장하고 있다. num =1, ret①에서 1B에서 시작하는 재귀함수 호출 실행한다. permu(1B)에서 이제 num=2에 대한 one, two에서 one = 2A2B비용, two = 2B2A 비용을 저장하고 있다! num=2가 마지막 숫자이고, 이미 각 경우에 대한 비용을 다 구했기 때문에 둘 중에 최소 비용을 리턴하면 된다! (num=2가 마지막 숫자이기 때문에 두개의 ret에서 재귀함수를 호출하더라도 0이 리턴되므로 결국 num=2의 one, two 중 최솟값을 리턴하는 것으로 된다.) => num=1, ret①으로 인해 1A1B에서 (2A2B, 2B2A )최솟값을 저장하고 있다!⭐️⭐️⭐️⭐️⭐️ 그러니까 1A1B에서 가능한 경우의수를 구하며 최소 비용을 저장하고 있는 것이다. 마찬가지로 num=1, ret②에서 1B1A에서 (2A2B,2B2A) 최솟값을 구하여 저장다. num=1 ①ret = 1A1B 2최솟값 ②ret = 1B1A 2최솟값 ret = (ret①,ret②)

두번째 풀었을 때 bfs에서 틀린 부분 1칸 이동한 후 (nx,ny)에서 한칸더 이동했을 때의 좌표 범위체크한 후 이동가능하다면 그 좌표로 이동한다.

  1. 범위 초과 오류 : j-for문에서 범위체크 후 좌표이동을 시켜야하는데 범위체크한 좌표로 이동하지 않고 j-for문 밖의 if(!visited)에서 (nx,ny)에 대해 연산을 수행하려고 하니까 범위체크한 것은 ㄴ무의미해진다. 스코프가 범위체크한 스코프를 벗어난 좌표이기 때문이다!

  2. j-for문으로 이동 가능할 때까지 반복 이동한 후에, 그 이동한 최종 좌표에 대해 중복방문 검사해서 큐에삽입&방문처리해줘야한다. 따라서 j-for문 밖에서 수행해줘야하는데 안에서 수행해줘서 틀렸다.

for(int d=0;d<4;d++){
                int nx = cur.x+dx[d];
                int ny = cur.y+dy[d];
                    
                if(check(nx,ny)) continue;
                if(!visited[nx][ny]){
                    visited[nx][ny] = true;
                    q.add(new Point(nx,ny,cur.cnt+1));
                }
                //Ctrl+방향키 처리.더 이동가능하다면 1칸 더 이동한 위치에서 더 이동.
                for(int j=0;j<2;j++){
                    if(Board[nx][ny] != 0) break;//숫자칸 도착하면 종료!
                    //동일한 d방향으로 더 이동한 좌표 범위  체크 후 이동시킨다!
                    if(check(nx+dx[d],ny+dy[d])) break;
                }
                //이동하고 난 후에! 반복 이동 스코프 벗어나야함!범위 이내이면 한번 더 이동! 큐에 삽입!
                if(!visited[nx+dx[d]][ny+dy[d]]){
                    visited[nx+dx[d]][ny+dy[d]] = true;
                    nx += dx[d];
                    ny += dy[d];

                    q.add(new Point(nx,ny,cur.cnt+1));
                }
            }

범위체크한 후 그 스코프에서 바로 이동시키는 것이 맞다. 그런데 if(!visiteed[nx][ny])가 이동을 반복하는 j-for 안에 있음으로써 틀린 이유는?

j-for문으로 이동가능할 때까지 다 이동한 후의 좌표(nx,ny)에 대해서 방문처리&큐삽입 해야한다.하지만 이동하는 족족 그 좌표들을 방문처리&큐삽입을 해버린다. =>엣지케이스에서 틀리게 됨.

for(int j=0;j<2;j++){
  if(Board[nx][ny] != 0) break;//숫자칸 도착하면 종료!
  //동일한 d방향으로 더 이동한 좌표 범위  체크 후 이동시킨다!
  if(check(nx+dx[d],ny+dy[d])) break;
  nx += dx[d];
  ny += dy[d];
  if(!visited[nx][ny]){
    visited[nx][ny] = true;
    q.add(new Point(nx,ny,cur.cnt+1));
  }
}

올바른 코드 : 이동 반복하는 j-for문 밖에 if(!visited)가 있어야함. 논리적으로도 최종이동한 좌표에 대해서 방문체크&큐삽입이 이루어져야하는 것이기 때문에 j-for문 밖에 있는 것이 맞다.

1칸씩 이동하는 일반적인 경우라면 맞을 수도 있지만, 1칸씩 이동가능한 만큼 모두 이동한 다음 최종 이동한 좌표에 대해서 수행해야하기 때문이다.

for(int j=0;j<2;j++){
  if(Board[nx][ny] != 0) break;//숫자칸 도착하면 종료!
  //동일한 d방향으로 더 이동한 좌표 범위  체크 후 이동시킨다!
  if(check(nx+dx[d],ny+dy[d])) break;
  nx += dx[d];
  ny += dy[d];
}
if(!visited[nx][ny]){
    visited[nx][ny] = true;
    q.add(new Point(nx,ny,cur.cnt+1));
  }

Previous5. 광고 삽입Next6. 매칭 점수(문자열 파싱)

Last updated