[백준] Q1987 알파벳 Gold IV
https://www.acmicpc.net/problem/1987
1987번: 알파벳
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으
www.acmicpc.net
1. 문제의 유형 및 이해
backtracking, 그래프 탐색(DFS)
세로 R, 가로 C칸의 보드 각 칸에 알파벳이 적혀있고 좌측 상단 칸에 말이 놓여 있다.
말이 상하좌우 인접한 네칸 중 한칸으로 이동할 때 조건이 있다.
- 지금까지 지나온 모든 칸에 적혀있는 알파벳과 달라야 한다.
- 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
최대 몇칸까지 지날 수 있는가?
어떠한 칸 (x,y)에 있을 때 항상 같은가? 라고 생각해보면 같지 않습니다.
A -> B -> C (x,y)와 D-> A -> C(x,y)는 다르니까요. 하지만, A->B->C와 B->A->C의 경로로 도착한 (x,y)는 같은 것으로 취급할 수 있습니다.
'어떠한 알파벳을 포함해 왔는지' 라는 상태를 파악해야 합니다.
그래프를 탐색하는데 있어 BFS, DFS 방식이 있을 때 상태 또는 분기점, 확산 방식에 따라 구분을 하게 되는데,
BFS를 사용했을 때 퍼져나가는 각각의 상태를 따로따로 저장해두기에는 불편하다고 생각하고 , 갈 수 있는 길을 모두 가보아야한다는 점에서 DFS가 맞다고 생각하였습니다.
또한 퍼져나가면서 어떠한 특정한 조건에 부딪히면 다시 돌아가서 확인해야하기 때문에 backtracking이라고 생각했습니다.
2. 문제 접근
DFS라는 탐색방법으로 Backtracking 알고리즘을 수행하자고 생각하고 보았을 때 정해야할 것이 몇개 있습니다.1. 현재 상태는? 각각의 상태를 따로따로 저장해두기 불편하다는 점에서 BFS가 아닌 DFS로 정하였습니다. 알파벳을 저장해두면서 갔다가 아니라면 그 부분을 빼주면 되니까요. 1.1 boolean 배열 활용. 알파벳 대문자만 들어온다고 하였으므로 boolean[] alphabet = new boolean[26]을 두고 확인하면서 true/false로 활용합니다. 이때 dfs()를 호출하기 이전에 해당 알파벳을 true로 해두고, 이후 false로 다시 돌려놓아야 합니다. 1.2 bit 연산활용. 요즘 bit 활용이 재밌어서 int형 안에 처리가 가능하다면 (int형 2^ 32) 방문 여부를 bit로 처리합니다. 쉬프트 연산과 or연산 and연산등을 활용하여 2진수로 바꾸었을 때 위치를 자신의 위치로 기억합니다. 예를 들어 'C'라면 알파벳에서 3번째 위치가 되고, 1<<(3-1) 을 상태에 or연산으로 masking해두면 status = ~~~ 100(2) 가 되고, 이후에 어떠한 칸 C를 마주쳤을 때 status = ~~~~~~~~~~~~~~~~~~~~~100 masking = 00000000000000000000000100을 &연산하였을 때 3이 나온다면(또는 0보다 크다면) 그전 상태에서 C를 지났다는 뜻이 됩니다.
2. Backtracking이라면 Pruning(가지치기)지! 어떠한 조건에서 다시 돌아 갈 것이냐 하는 것입니다. backtracking에서 promising function은 속도 향상에 큰 영향을 줍니다. 이 문제의 경우 조건으로 '지나오지 않은 알파벳일때'라는 조건이 있어서 이를 활용하여도 좋습니다. 기존에 많이 사용하던 true/false 문제도 해결 가능하기 때문입니다.하지만 단순 boolean visited배열은 사용하거나 사용하지 않거나 어차피 '지나오지 않은 알파벳일 때'라는 조건에 걸리기 때문에 속도향상에 큰 영향을 주지 않습니다.
하지만 다음과 같은 경우는 조금 다릅니다.
A B C
B F C 라는 맵이 있을 때
F에 도달하는 ㄱ 자 모양 (ABF)와 ㄴ자 모양(ABF)를 보았을 때 도착한 경로는 다르지만 결국, 같은 상태, 같은 위치가 됩니다.
이러한 연산들을 반복적으로 하게되었을 때 시간이 많이 늘어날 수 있습니다. 이러한 것을 해결하기 위해 만약,
ㄱ자 모양으로 F에 도달하였을 때 F에 A,B로 해서 온적이 있음! 이라고 저장을 해둔 다음 모든 경우를 다녀옵니다.
이후 ㄴ자 모양으로 F에 도달하였을 때 이미 A,B로 해서 왔다간적이 있음 이라는 것을 보고 더이상 가지 않는다면, 이후의 위치는 어차피 다녀온 길이니 가지 않아도 되겠죠. 큰 그래프에서 이러한 경우가 초반이나 몇번 걸리기라도 한다면 크게 단축 시킬 수 있을 것입니다.
물론,
A B C
C F D 와 같은 위치에서 F는 큰 역할을 하지 않을 지도 모르지만, 문제를 푸는데 영향을 주지 않으면서 한번이라도 잡을 수 있다면 시간을 줄일 수 있다는 점에서 의미가 있습니다.
/*
2022.01.11
문제번호 : Q1987
이름 및 난이도 : 알파벳 Gold IV
문제이해
-----------------
세로 R칸, 가로 C칸 모양 보드.
각 칸에 대문자 알파벳이 하나씩. 좌측(1행 1열) 말이 있다.
말은 상하좌우 인접한 네 칸 중 한칸 이동.
(새로 디오한 칸에는 지나온 모든 칸에 적혀있는 알파벳과 달라야한다.)(같은 알파벳 두번 X)
좌측 상단에서 말이 최대한 몇 칸을 지날 수 있는가?
제한 조건 :
R, C <= 20
접근 방법 :
2^26의 상태. 2^26 = 67_108_864 >> 상태의 확인 bit
back tracking 으로 가본다. with dp
back tracking으로 가는 건 너무 많은 경우의 수와
중복의 경우의 수가 있음.
→ ← ↑ ↓
→ → 로 도착한 경우와
↑ → → ↓ 로 도착한 칸 의 위치는 같지만 상태는 다르다.
dp로 해결하는데 어려움이 있다.
backtracking..다시 돌아가는 건 안됨.(중복 X)'
1. bfs
>> bfs로 하기에 상태공간의 정의가 [R][C][2^26] 이 되어야함.
2. dfs
>> dfs로 할 시에 중복의 관리는 bit계산을 통한 현재 상태를 통해 진행한다.
>> depth가 깊어봐야 26이라고 생각함.
>> 채택
++ bit가 아니라 boolean[26]으로도 가능하다.
역시 backtracking promising 에 따라 달라진다 속도가.
3. dp (X)
dp는 작은 문제를 풀었을 때 큰 문제를 풀어야하나.
→ → 로 도착한 경우와
↑ → → ↓ 로 도착한 칸 의 위치는 같지만 상태는 다르다.
dp로 해결하는데 어려움이 있다.
*/
import java.io.*;
import java.util.*;
public class Main {
static int cnt = 1;
static int R, C;
static char[][] map;
static int[][] visit;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new char[R][C];
for (int i = 0; i < R; i++) {
map[i] = br.readLine().toCharArray();
}
int status = 1 << map[0][0] - 'a';
visit = new int[R][C];
dfs(0, 0, status, 1);
System.out.println(cnt);
}
static int[][] dir = new int[][] { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
public static void dfs(int r, int c, int status, int depth) {
if (visit[r][c] == status)
return;
visit[r][c] = status;
boolean isEnd = true;
for (int i = 0; i < 4; i++) {
int nx = dir[i][0] + r;
int ny = dir[i][1] + c;
if (nx < 0 || ny < 0 || nx > R - 1 || ny > C - 1)
continue;
if ((status & 1 << map[nx][ny] - 'a') > 0)
continue;
isEnd = false;
dfs(nx, ny, status | 1 << map[nx][ny] - 'a', depth + 1);
}
if (isEnd) {
cnt = Math.max(cnt, depth);
}
}
}3. 배운점
사실 방문 여부 check를 하지 않아도 풀 수 있는 문제이다. 실제로 방문 여부를 체크하지 않고 풀었을 때
시간이 꽤 많이 걸렸었고, 다른 사람들과 시간 차이가 많이 나서 확인해 보았을 때의 차이는 방문 여부 체크였다.
사실 visit배열을 통해 단순 true/false로 비교하는 것은 bit연산이나 boolean 배열에서 해당 값이 있는지 없는지 확인하는 정도로 비교하면 되서 크게 차이가 나지 않는다.
하지만, visit배열에 지금까지 들어온 status 값을 기록해둔다면 위에서 설명한 것 처럼 하나라도 걸리면 크게 시간을 단축시킬 수 있다는 점에서 좋다.
backtracking에서 pruning연산의 퀄리티에 따라 속도가 차이나는 것을 알고 있었지만, 체감한 것은 처음이라서 조금 더 신경써야되고 고려해줄 수 있다면 고려해주는 것이 좋겠다 라는 것을 알았다.