[백준] 1987번: 알파벳 Python - DFS/Backtracking

https://www.acmicpc.net/problem/1987

1987번: 알파벳

시간초과 풀이 

단순하게 구현했더니 시간초과 난다 ㅎㅎ 

import sys 
input = sys.stdin.readline 

r, c = map(int, input().split())
board = []
for i in range(r):
    data = input()
    temp = []
    for j in range(c):
        temp.append(data[j])
    board.append(temp)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

answer = 0 
visited = [[False] * c for _ in range(r)]

def check(i, j, route):
    if 0 <= i < r and 0 <= j < c and not visited[i][j]:
        if board[i][j] not in route:
            return True
    return False 

def dfs(x, y, route):
    global answer
    count = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if check(nx, ny, route):
            route.append(board[nx][ny])
            visited[nx][ny] = True
            dfs(nx, ny, route) 
            visited[nx][ny] = False 
            route.pop(-1)
        else:
            count += 1
    if count == 4:
        answer = max(answer, len(route))
        return 
            

visited[0][0] = True 
dfs(0, 0, [board[0][0]])
print(answer)

 

 

정답 코드

기존 코드의 문제점

나는 이전에 route 라는 리스트에 경로를 지나면서 얻은 알파벳들을 넣어주었다. 

그런데 이 과정에서 알파벳이 있나 없나 확인할 때 in 연산을 사용했다.

in 연산을 쓰는 것을 피하고 다른 방법을 떠올려야 한다. ---> 백트래킹

우선 저 in 연산의 시간복잡도는 자료구조형 마다 다른데, list 의 경우 O(N) 이 된다. 연속적으로 하나씩 스캔하면서 값을 찾기 때문 

이 O(N) 연산을 효율적으로 바꿔주기 위해서 백트래킹으로 풀 수 밖에 없다....

 

해결 방법 

알파벳은 26개 밖에 안된다. 따라서 알파벳을 담을 수 있도록 저장공간을 할당한다. 

visited = [0]* 26 # alphabet 개수만큼 메모리 할당

그리고 이 visited 에 저장된 값으로 현재 확인중인 알파벳이 이미 탐색되었는지 아닌지를 구별할 수 있다. 

또한 상하좌우 네 방향으로 경로를 탐색하는데, 이 경우 백트래킹을 구현하기 위해서 사용한다. 

alpha2num = ord(board[nx][ny]) - 65
visited[alpha2num] = True
dfs(nx, ny) 
visited[alpha2num] = False

 

 

import sys 
input = sys.stdin.readline 
# A 65 ~ Z 90 
# print(ord('A'))
# print(ord('Z')-65)

r, c = map(int, input().split())
board = []
for i in range(r):
    data = input()
    temp = []
    for j in range(c):
        temp.append(data[j])
    board.append(temp)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

answer = 0 
visited = [0]* 26 # alphabet 개수만큼 메모리 할당 

def check(i, j):
    if 0 <= i < r and 0 <= j < c:
        alpha2num = ord(board[i][j]) - 65
        if not visited[alpha2num]:
            return True
    return False 

def dfs(x, y):
    global answer
    count = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if check(nx, ny):
            alpha2num = ord(board[nx][ny]) - 65
            visited[alpha2num] = True
            dfs(nx, ny) 
            visited[alpha2num] = False 
        else:
            count += 1
    if count == 4:
        answer = max(answer, sum(visited))
        return 
            
start = ord(board[0][0])-65
visited[start] = True 
dfs(0, 0)
print(answer)