[Gold IV]
https://www.acmicpc.net/problem/1987
1987번: 알파벳
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으
www.acmicpc.net
풀이 1
이건 그냥.. DFS, Backtracking 이용해서 Recursion으로 풀면 되겠다- 라고 간단하게 생각했다.
그런데 가볍게 짠 코드에서 TLE.
import sys
sys.setrecursionlimit(100000)
R, C = map(int, input().split())
board = [list(input()) for _ in range(R)]
result = []
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
def dfs(i, j, depth, visited: dict):
global maxDepth
if visited.get(board[i][j], 0) == 1 or depth == R*C:
return
visited[board[i][j]] = 1
result.append(depth)
for k in range(4):
di = i + dy[k]
dj = j + dx[k]
if 0 <= di < R and 0 <= dj < C:
dfs(di, dj, depth+1, visited)
if visited.get(board[i][j]):
visited[board[i][j]] = 0
dfs(0, 0, 1, {})
print(max(result))
풀이 2
recursion을 덜 하도록 최적화하여 수정.
60~80%? 후반부쯤에서 TLE.
import sys
sys.setrecursionlimit(100000)
R, C = map(int, input().split())
board = [list(input()) for _ in range(R)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = {}
maxDepth = 0
def dfs(i, j, depth):
global maxDepth
if maxDepth < depth:
maxDepth = depth
for k in range(4):
di = i + dy[k]
dj = j + dx[k]
if 0 <= di < R and 0 <= dj < C and visited.get(board[di][dj], 0) != 1:
visited[board[di][dj]] = 1
dfs(di, dj, depth+1)
visited[board[di][dj]] = 0
visited[board[0][0]] = 1
dfs(0, 0, 1)
print(maxDepth)
풀이 3
로직 자체는 맞는 것 같은데, python의 특성 때문에 느린 건지 - dictionary를 사용하여 느린 건지 싶어서 visited를 array로 바꿔서 풀었음.
AC.
import sys
sys.setrecursionlimit(100000)
R, C = map(int, input().split())
board = [list(input()) for _ in range(R)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = [0]*26
maxDepth = 0
def dfs(i, j, depth):
global maxDepth
if maxDepth < depth:
maxDepth = depth
for k in range(4):
di = i + dy[k]
dj = j + dx[k]
if 0 <= di < R and 0 <= dj < C and visited[ord(board[di][dj])-65] != 1:
visited[ord(board[di][dj])-65] = 1
dfs(di, dj, depth+1)
visited[ord(board[di][dj])-65] = 0
visited[ord(board[0][0])-65] = 1
dfs(0, 0, 1)
print(maxDepth)