백준 1987 문제 링크: https://www.acmicpc.net/problem/1987
📑 문제 설명
1. R, C 행렬이 주어지며 각 행렬은 알파벳으로 구성되어 있음
2. 좌측상단에서 시작하여 상, 하, 좌, 우로 한 칸씩 움직일 수 있으나 이미 지나친 알파벳은 또 지날 수 없음
3. 2번을 지키면서 좌측상단으로부터 가장 멀리 갈 수 있는 최대 거리 구하기
입력: 첫 번째 줄에 행, 열인 R과 C가 주어짐(공백으로 구분됨)
두번째 줄부터 R개 줄에 걸쳐서 보드에 적혀있는 C개의 대문자 알파벳이 빈칸 없이 주어짐 --> 대문자는 C개까지 출력되나 알파벳은 총 26개이므로 visited 배열에 26개 선언하고 시작해도 됨
출력: 최장 거리
💡 문제 해결 방법
알고리즘: DFS
알고리즘 선택 이유
1. 넓게 가는 것이 아닌 깊게 멀리 가야하기 때문에
2. 분기별로 최장 길이를 구하여 비교해야 하기 때문에
예외처리
- 갈 수 없는 곳(좌측상단일 경우 좌, 상으로 이동할 수 없음) 처리
- dfs 가 끝나는 지점에서 visited를 False로 알파벳은 가장 최근에 들어간 알파벳을 제거해주어야 함 --> 이걸 하지 않으면 이미 방문한 것으로 간주하여 최적의 루트를 찾을 수 없음
- dfs 종료조건으로는 더 이상 나아갈 길이 없을 경우 종료
- 재귀 함수에서 max 값을 비교해야 하는데 이 부분 어떻게 하는 지 모름 --> 하단 코드 참고(global dist 식으로 변수 선언하면 재귀 함수 내에서 비교 가능)
스터디 내용
- 위치 저장은 필요 없고 알파벳 visited(26개) 필요함
- 백트래킹 시 visited 초기화 --> detph 변수 사용
- global max_depth
해결 방법
1. 알파벳만 visited 배열로 체크해 주면 됨 --> 굳이 이동하는 곳(즉 버택스는 체크 불필요)
2. 최장 거리를 비교해야 하기 때문에 방문을 완료했을 때 최적인지 아닌지 모르므로 백트래킹하여 최적의 거리 검색
3. DFS
💻 코드
import sys
r, c = list(map(int, sys.stdin.readline().split()))
graph = [[0 for x in range(c)] for x in range(r)]
for i in range(r):
temp = sys.stdin.readline()
for k in range(c):
graph[i][k] = temp[k]
visited = [False for x in range(26)]
def dfs(x, y, visited, depth):
global dist
dist = max(dist, depth)
n = graph[x][y]
visited[ord(n)-65] = True
adj_list = [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]
check = 0
for point in adj_list:
px = point[0]
py = point[1]
if px >= 0 and px < r and py >=0 and py < c:
n = graph[px][py]
if visited[ord(n)-65] == False:
check += 1
dfs(px, py, visited, depth + 1)
visited[ord(n)-65]=False
global dist
dist = 0
dfs(0, 0, visited, 1)
print(dist)💟 추가적으로 알게 된 점
- global [변수명] 으로 재귀 함수 내에서 값 비교 가능
- 최장거리 탐색 시 백트래킹 사용
- 나 같은 경우 사용한 알파벳 및 이동한 버택스 까지 visit을 체크하는 바람에 틀림/시간초과 뜸 --> 필요없는 배열이 있는지 고민할 필요
- for nx, ny in adj_list: 로 하고 nx, ny에 접근하면 시간 초과가 뜬다.. 이유는 몰라..
