| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 112859 | 33642 | 20494 | 28.281% |
문제
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
입력
첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.
출력
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.
답안
import sys
height, width = map(int, sys.stdin.readline().split())
board = [list(map(lambda x: ord(x) - ord('A'), sys.stdin.readline().rstrip()))
for _ in range(height)]
history = [False for _ in range(26)]
history[board[0][0]] = True
delta = ((1, 0), (-1, 0), (0, 1), (0, -1))
answer = 0
def dfs(row, col, depth, history):
global answer
history[board[row][col]] = True
depth += 1
answer = max(answer, depth)
for dr, dc in delta:
r, c = row+dr, col+dc
if 0 <= r < height and 0 <= c < width and not history[board[r][c]]:
dfs(r, c, depth, history)
history[board[row][col]] = False
dfs(0, 0, 0, history)
print(answer)주의: 이 풀이는 Python3에서는 시간초과 판정을 받습니다. PyPy로 제출해야 정답 판정을 받을 수 있습니다.
풀이
이 문제에서 보드의 크기가 20*20의 작은 크기로 주어지기도 하고, 모든 경우를 탐색하지 않고는 가장 긴 경로를 찾을 수 없기 때문에, 모든 경우의 수를 탐색하는 풀이를 생각해볼 수 있을 것이다.
다만 이 문제는 시간이 아주 타이트하게 잡혀 있어서, 모든 경우의 수를 탐색하는 것보다도 그것을 어떻게 최적화할지가 가장 포인트라고 할 수 있다.
이 문제는 일반적인 BFS나 DFS와 같이 visited 배열을 써서 어느 칸을 방문했는지 확인할 필요가 없고, 그 칸을 방문했다고 해서 재방문을 막는 일은 더더욱 해서는 안된다.
여러 경로들이 있을 텐데, 한 경로와 또다른 경로가 경유하는 칸이 겹칠 수 있기 때문이다.
그 대신에 지금까지 방문했던 알파벳 종류가 무엇인지는 기록해야 한다. 문제 조건상 같은 알파벳이 적힌 칸은 다시 밟을 수 없기 때문이다.
그렇다면
- 어떻게 모든 경로들을 순회시킬 것인가?
- 어떻게 지금까지 방문했던 알파벳 정보들을 관리할 것인가?
import sys
sys.setrecursionlimit(500)
height, width = map(int, sys.stdin.readline().split())
board = [list(map(lambda x: ord(x) - ord('A'), sys.stdin.readline().rstrip()))
for _ in range(height)]
answer = 0
def get_adjacents(row, col, history):
result = list(filter(lambda x: 0 <= x[0] < height and 0 <= x[1] < width
and not history[board[x[0]][x[1]]],
[(row-1, col), (row+1, col), (row, col-1), (row, col+1)]))
return result
def dfs(row=0, col=0, depth=0, history=[False for _ in range(26)]):
global answer
history[board[row][col]] = True
depth += 1
answer = max(answer, depth)
for r, c in get_adjacents(row, col, history):
dfs(r, c, depth, history[:])
dfs()
print(answer) 내가 맨 처음에 제출한 코드이다. 위 답안과 큰 차이점을 보이지 않지만, 차이점이라면 get_adjacents()라는 함수를 따로 분리하여, 이를 이용해 문제를 풀었다는 점과 dfs(r, c, depth, history[:])와 같이 재귀 호출되는 함수마다 각각의 리스트 객체를 가지도록 만들었다는 점이다.
이런 이유 때문에, 이 코드는 Python3과 PyPy3 구현체에서 모두 시간 초과 판정을 받았다.
리스트를 복사하는 일은 아주 비싼 작업이라는 사실을 이전 문제를 풀었던 경험상 알고 있었기 때문에, 리스트를 복사하지 않고도 풀이가 가능하도록 변경해보았다.
import sys
height, width = map(int, sys.stdin.readline().split())
board = [list(map(lambda x: ord(x) - ord('A'), sys.stdin.readline().rstrip()))
for _ in range(height)]
history = [False for _ in range(26)]
history[board[0][0]] = True
answer = 0
def get_adjacents(row, col, history):
result = list(filter(lambda x: 0 <= x[0] < height and 0 <= x[1] < width
and not history[board[x[0]][x[1]]],
[(row-1, col), (row+1, col), (row, col-1), (row, col+1)]))
return result
def dfs(row, col, depth, history):
global answer
history[board[row][col]] = True
depth += 1
answer = max(answer, depth)
for r, c in get_adjacents(row, col, history):
dfs(r, c, depth, history)
history[board[row][col]] = False
dfs(0, 0, 0, history)
print(answer)각 칸을 방문할 때마다, history 배열에 현재 칸의 알파벳 번호를 기록하고, 그 칸을 벗어날 때마다 현재 칸의 알파벳 번호를 기록했던 것을 지우도록 했다.
이렇게 하면 재귀 깊이를 왔다갔다 하면서 하나의 history 배열로도 처리가 가능해진다.
하지만, 이렇게 PyPy3로 제출해보았는데도 시간 초과로 오답 판정을 받았다.
def dfs(row, col, depth, history):
global answer
history[board[row][col]] = True
depth += 1
answer = max(answer, depth)
for dr, dc in delta:
r, c = row+dr, col+dc
if 0 <= r < height and 0 <= c < width and not history[board[r][c]]:
dfs(r, c, depth, history)
history[board[row][col]] = False그래서 위와 같이 구현을 바꿔, get_adjacents()가 했던 일들을 역리팩토링해봤는데, 이렇게 하니 PyPy3 기준으로 정답입니다 판정을 받을 수 있었다.
‘시간 초과’를 받은 코드와 ‘정답입니다’를 받은 코드를 비교해봤을 때, 백준 채점 중에 퍼센트가 올라가는 속도가 눈으로 보일 정도였다.
내부적으로 반복문으로 구현되어 있을 테니까 일반 반복문과 filter()가 비슷한 성능을 낼 것이라고 생각했었는데, 생각보다 유의미한 차이를 냈던 것이다.
아니면, get_adjacents() 함수를 불러 다음 깊이로 나아가야 할 때, [(row-1, col), (row+1, col), (row, col-1), (row, col+1)] 리스트를 항상 새로 만들어야 했다는 점이 시간 차이를 가져온 것일지도 모르겠다.
따라서, 이 문제를 통해 배운 점은 다음과 같다.
- Python에서는 리스트를 새로 만드는 것이 생각보다 무겁다.
filter()와 같이 함수형 프로그래밍을 할 때 사용할 수 있는 도구들의 성능이 생각보다 떨어질 수 있다.
