비트필드를 이용한 DP에 대해서 지난 글에 설명을 하였으니, 이번에는 접한 문제에 대해 간단하게 다루도록 하겠다.
오늘도 어김없이 알고리즘 연습을 하고 있는데 익숙한 문제를 만났다.
문제는 백준 1987: 알파벳이다. 요구 사항은 character로 이루어진 이차원 배열에서 character가 겹치지 않는 최장 루트를 구하는 것으로 간단하다. Set를 이용한 Naive한 구현은 정말 쉬워 보여서 바로 풀었다. 근데 웬걸, 가장 빠른 코드보다 10배나 느린 것이다.
급하게 HashSet의 add, remove, contains의 시간 복잡도를 찾아봤는데 O(1)이라고 한다. 그럼 도대체 왜..
알아보니 다른 분들은 일종의 비트필드를 이용한 DP를 이용한 것이었다. 알파벳이라고 했을 때 바로 눈치챘어야 했는데 아직도 비트마스킹 문제를 한눈에 못알아본 나의 실책이었다. 요점은 아래와 같다.
내가 구현한 알고리즘은 깃허브에서 확인이 가능하다. 이는 일반적으로 DFS를 할 때 사용하는 visit을 HashSet으로 대체한 것이 핵심이고 이것 외에는 특별할 것이 없다. 최대 원소 수는 이지만 한 루트의 최대 길이는 이고 한 좌표에서 갈 수 있는 최대 선택지는 이므로 N이 클 경우에 N에 대해 완전 탐색은 아니기에 적용했지만 쓰다 보니 최악의 경우는 으로 꽤나 오래 걸린다. (계산에 문제가 있으면 댓글로 알려주세요)
위의 이유로 중복되는 루트는 한번만 계산하도록 해야하는데, 이때 비트마스킹이 필요하다.
우선 비트마스킹이 왜 필요한지 보자. 좌표 (i, j)에 처음 도달했는데 현재까지 {'A', 'B', 'C', 'D'}의 문자를 확인했다고 생각해보자. 그러면 다음에 (i, j)에 올 때 만약 동일하게 {'A', 'B', 'C', 'D'}의 루트로 도착했다면 더이상 계산을 하지 않아도 된다. 이는 기존의 계산으로 이미 해당 케이스가 커버되었기 때문이다. 혹자는 도달한 방향이 다르니 다시 확인해야한다라고 생각할 수 있지만 그렇지 않다. (i, j)가 배열의 변두리가 아니어서 총 4개의 선택지가 있다고 가정하자. 이 중 루트 A와 B로 각각 {'A', 'B', 'C', 'D'} 문자를 거쳐 (i, j)로 도착했다면 애초에 A와 B는 서로 통하지 못하는 루트이다. A로 (i, j)까지 왔다면 애초에 (i, j)에서 B루트로 가려면 {'A', 'B', 'C', 'D'} 문자 중 하나를 거쳐야하기 때문. 때문에 이런 경우 추가 탐색을 하지 않고 바로 해당 탐색을 종료(return)해도 된다.
