파이썬(python) 백준 1987 : 알파벳

1987번: 알파벳

 

문제 내용

시간 제한 : 2 초

메모리 : 256 MB

 

공간

• RxC 크기의 공간 (각 좌표마다 알파벳 쓰여있음)

등장인물

• 말 : (1,1) 위치에 놓여있음

동작

말을 상하좌우로 이동한다. 아래의 제약 조건 있음.

• 각 알파벳을 2번 이상 밟고 지나갈 수 없음.

 

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20)

둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

 

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

 

예제 입력 1

2 4

CAAB

ADCB

 

예제 출력 1 

3

유형

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색
• 백트래킹

---

풀이

전형 적인 탐색 문제에 약간의 테크닉이 첨가되어야 하는 문제다.

각 알파벳을 2번 이상 밟고 지나갈 수 없으면서 최대한 많은 칸을 밟아야 한다.

즉, 각 위치를 여러가지 경로로 중복해서 방문할 수 있다는 가능성을 열어 두어야 한다.

예를 들면 (2,2) 위치를

A-B-C 로도 올 수 있고, A-C-B 로도 올 수 있다.

 

문제는 중복 방문을 허용하게 되면 시간과 메모리를 많이 잡아 먹는다.

그래서 중복 검사를 아주 효율적으로 해야하는 테크닉이 필요하다.

1. visited (방문 검사 배열) 에 경로 자체를 저장한다.
   해당 위치에 다른 경로로 도달했을 경우에만 갱신하고 큐 또는 리스트에 넣는다.
2. 문자열 (str, 텍스트 시퀀스)의 +연산은 실제로 새로운 str 객체를 생성해야 되는 방식이므로
   꽤 많은 시간을 잡아먹는다. 따라서 문자열 그대로 저장하지 않고 비트로 변환하여 저장한다.
   A-B의 경우 'AB'로 저장하지 않고 2진수 11로 저장되는 방식이다. 

import sys
r,c = map(int,sys.stdin.readline().split())
board = [list(sys.stdin.readline().rstrip()) for _ in range(r)]
visited = [[[] for _ in range(c)] for _ in range(r)]
result = 0
dx = (-1,1,0,0)
dy = (0,0,1,-1)
A  = ord('A')
q = ([(0,0,1,1<<(ord(board[0][0])-A))])

while q and result < 26:
    x, y, cnt, cur_bit = q.pop()
    result = max(result, cnt)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < r and 0<= ny <c:
            seq = ord(board[nx][ny])-A
            if cur_bit & (1<<seq) == 0 :
                next_bit = cur_bit | 1<<seq
                if visited[nx][ny] != next_bit:
                    visited[nx][ny] = next_bit
                    q.append((nx,ny,cnt+1,next_bit))
print(result)