[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)