알파벳 - 1987

[Gold IV] 알파벳 - 1987

문제 링크

성능 요약

메모리: 150972 KB, 시간: 7712 ms

분류

백트래킹(backtracking), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

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

DFS 풀이

• DFS를 이용하기 위한 재귀 함수를 이용한다.
• valid한 방향(보드 안의 좌표 값 and 지나온 칸의 알파벳이 아닌 경우) 해당 지점을 set에 추가 한 후 DFS 진행, 말이 더 이상 진행을 하지 못 할 때 백트래킹을 하기 위해 재귀 리턴으로 갈림길 지점으로 돌아와서 다른 방향으로의 진행을 한다 이때 추가 한 지점으로의 DFS는 완료 했기 때문에 set에서 제거 해준다.
• 문제의 결과 값은 최대의 칸 수 이기때문에 각각의 DFS 에서의 최대 거리를 기록하기 위해 전역변수를 공통으로 사용하고 갱신한다.

코드

# r : 세로, c : 가로
r, c = map(int, input().split())

# 각 칸에 알파벳이 들어 있는 보드 
board = []
for _ in range(r):
    board.append(list(input()))

# 중복 방지를 위해 set
visit_alpha = set()

# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# max count값을 기록할 ans
# 최고 멀리 간 지점까지의 거리만 기록하면 됨
ans = 0

def dfs(x, y, count):
    # 다른 함수에서도 공통인 ans를 사용하기 위함
    global ans
    # 최고 지점을 기록하기 위해
    ans = max(count, ans)
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0<= nx < r and 0<= ny < c and not board[nx][ny] in visit_alpha:
            visit_alpha.add(board[nx][ny])
            # 막힐 때 까지 최고 지점까지 
            dfs(nx, ny, count+1)
            # 백트래킹 하기 위하여 
            # 막힌 부분에 도달하고 돌아왔을 때 다른 루트로 가기 위함
            visit_alpha.remove(board[nx][ny])


visit_alpha.add(board[0][0])    
dfs(0, 0, 1)
print(ans)

---

문제점

이 코드를 python3로 제출을 했을 때 시간초과의 결과가 일어난다. r, c가 20밖에 되지 않지만 보드의 각 격자 칸들은 가장자리를 제외하고 대부분의 칸에서 다음 4칸으로 진행할 수 있다. 왔던 칸을 제외하면 3칸이므로 경우의 수가 3의 거듭제곱 꼴로 늘어나기 때문이다. 따라서 해결방법으로는 pypy3를 사용하는 것이다. 이유가 궁금하여 검색한 결과 pypy는 JIT컴파일을 도입하여 CPython보다 빠르다는 것이다. 즉 pypy에는 자주 쓰이는 코드를 캐싱하는 기능이 있기 때문에, 메모리를 조금 더 사용하여 실행속도를 개선하였고 반복문을 많이 사용하는 코드에서는 pypy가 속도 측에서 우세하다고 한다. (간단한 코드 상에서는 Python3가 메모리, 속도 측에서 우세할 수 있다.)

BFS 풀이

• BFS 방식 백트래킹
• 큐에는 좌표와 이때까지 지나온 알파벳들을 연결한 문자열을 넣고 뺌
• 방문 체크 배열 r * c개의 집합
• 각 칸까지 지나온 알파벳들이 동일하면 또 탐색하지 않아도 됨 즉 지나온 알파벳 문자열을 집합에 저장해 두고, 다음에 다시 이 칸을 방문할 때 지나온 알파벳 문자열이 이미 집합에 있다면 탐색을 더 진행하지 않고 가지치기

코드

from collections import deque
# r : 세로, c : 가로
r, c = map(int, input().split())

# 각 칸에 알파벳이 들어 있는 보드 
board = []
for _ in range(r):
    board.append(list(input()))
chk = [[set() for _ in range(c)] for _ in range(r)]
ans = 0

# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

dq = deque()
chk[0][0].add(board[0][0])
dq.append((0, 0, board[0][0]))
while dq:
    y, x, s = dq.popleft()
    ans = max(ans, len(s))

    for k in range(4):
        ny = y + dy[k]
        nx = x + dx[k]
        if 0<= ny < r and 0 <= nx < c and board[ny][nx] not in s:
            ns = s + board[ny][nx]
            # 지나온 알파벳 경로가 동일한 경로 같은 경우는
            # 같기 때문에 또 살펴보지 않아도 되게끔 함
            # [[A, B], [B, C]] 예를 들어
            # C까지는 오른쪽 B, 아래 C 또는 아래 B, 오른쪽 C
            # 어차피 지나온 경로가 같으니깐 C에서 나머지 탐색을 진행하는 것은
            # 결과가 동일 
            if ns not in chk[ny][nx]:
                chk[ny][nx].add(ns)
                dq.append((ny, nx, ns))
print(ans)