[백준/Python(파이썬)] 1987 알파벳

2021-02-03

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

1987번: 알파벳

오랜만에 푼 그래프 문제였음 dfs로 풀었는데 다른 풀이도 살펴보니 보통 bfs 많이 사용하는 편

시간초과 나와서 Pypy3으로 채점했음 

풀면서 했던 생각

1. 알파벳을 아스키코드를 이용해 int로 바꿔서 방문 표시 등에 용이하게 함

2. visited를 2차원 list가 아닌 알파벳 26자에 대한 단순 list 형태로 간단히 표현함

 

풀이 참고하기 전까진 2차원 배열로 만들고 있었음 당연히 더 복잡하게 풀고 있었다

그리고 아스키코드 변형 시 람다식을 이용해 입력 받을 때 바로 바꾸는 테크닉도 참고함

 

[소스코드]

import sys

input = sys.stdin.readline
def dfs(x, y, cnt):
    global ans
    ans = max(ans, cnt)

    for i in range(4):
        tx = x + dx[i]
        ty = y + dy[i]
        if 0<=tx<r and 0<=ty<c and visited[board[tx][ty]] != 1:
            visited[board[tx][ty]] = 1
            dfs(tx, ty, cnt+1)
            visited[board[tx][ty]] = 0
dx = (-1, 0, 1, 0)
dy = (0, 1, 0, -1)
r, c = map(int, input().split())
# 붙어있는 문자열 한 번에 입력 받기 ## CAAB => ['C', 'C', 'A', 'B']
# [list(input().rstrip()) for _ in range(r))
# map을 이용해 자른 문자를 아스키코드로 바로 변환
board = [list(map(lambda x: ord(x)-65, input().rstrip())) for _ in range(r)]
visited = [0] * 26
ans = 0

visited[board[0][0]] = 1
dfs(0, 0, 1)
print(ans)