[Python] 백준, 1987 (DFS)

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

1987번: 알파벳

개요

- dfs/bfs 형 기본 문제. 차별점은 숫자로 구성된 리스트가 아니라 알파벳 리스트이기 때문에 아스키 코드를 사용해야 효율성이 높아진다는 정도.

- [0][0] 값에서부터 dfs를 돌면서 거리값을 갱신한다. 재귀를 통해서 갈 수 있을 만큼 들어가기 때문에, dfs 루프가 끝나는 시점이 하나의 경우의 수가 된다.

- answer값을 갱신하는 방법은 구글링으로 참고했다. 아주 조금만 생각을 더 했더라면 내가 떠올렸을 수 있을 것 같은데 아쉽다.

 

아이디어

 - 처음엔 String 모듈을 통해 알파벳 대문자들을 받고, visit 딕셔너리에 각 값들을 False에 매칭 시키는 자료구조를 선택했다.

 

코드 풀이

- 4번째 줄 : map 함수가 알파벳의 아스키 코드에서 65를 빼준다. (A부터 각각 0의 값을 갖는 숫자 배열이 된다.)

- 11번째 줄 : answer 값을 global 선언 해준 뒤, 루프가 끝난 cnt(이동 거리) 값과 비교 후 최댓값 갱신.

- 21번째 줄 : 다음 경우의 수를 위해 값 초기화.

 

# PYTHON CODE

import sys

s, c = map(int, sys.stdin.readline().split())
seq = [list(map(lambda x: ord(x) - 65, sys.stdin.readline().rstrip())) for _ in range(s)]
visit = [0] * 26
answer = 0


def dfs(x, y, cnt):
    global answer
    answer = max(answer, cnt)

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

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < c and 0 <= ny < s and visit[seq[ny][nx]] == 0:
            visit[seq[ny][nx]] = 1
            dfs(nx, ny, cnt + 1)
            visit[seq[ny][nx]] = 0
    return answer


visit[seq[0][0]] = 1
dfs(0, 0, 1)
print(answer)