python 백준 1987 알파벳

백준 알파벳 문제

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

1987번: 알파벳

 

백준 1987 알파벳

- 첫 풀이(시간초과)

import sys


r, c = map(int,sys.stdin.readline().split())
matrix = []
for i in range(r):
    arr=[]
    temp = sys.stdin.readline().rstrip()
    for j in temp:
        arr.append(j)
    matrix.append(arr)


def dfs(start,visited2=[]):
    global maximum
## 방문한 알파벳 'A'등을 추가해줌 ##
    visited2.append(matrix[start[0]][start[1]])
## 방문한 알파벳 길이를 계속 업데이트 하여 최대값을 찾는다 ##
    if len(visited2) > maximum:
        maximum = len(visited2)
## matrix에서 현재위치와 연결된 다음 위치를 (x,y)리스트를 넣어줌 ##
    for node in graph[start[0],start[1]]:
        if matrix[node[0]][node[1]] not in visited2:
## node = [0,1]과같이 matrix위치로 구성되어있으며 다음 dfs로 recursion한다. ##
            dfs(node,visited2)
## 재귀가 다음 연결지점에 방문하지 못하고 나오면서 현재 저장되었던 알파벳 리스트를 없애줌 ##
## 다른경로로 갈때 새로 방문하여야 하기 때문 ##
            visited2.pop()

dx = [1,-1,0,0]
dy = [0,0,1,-1]
x,y = 0,0
count = 0
graph = dict()
## 딕셔너리 key value구조를 이용하여 node가 어떤 node들과 edge(간선)가 이어져있는지 저장 ##
for i in range(r):
    for j in range(c):
        temp = []
        for k in range(4):
            nx = j + dx[k]
            ny = i + dy[k]
            if nx<0 or nx>=c or ny<0 or ny >= r:
                continue
            else:
                temp.append([ny,nx])
        graph[i,j] = temp
maximum = 0
dfs([0,0])
print(maximum)

- 알파벳을 True False check를 이용하여(시간초과)

import sys

def aToIdx(a):
    return ord(a)-ord('A')


r, c = map(int,sys.stdin.readline().split())
matrix = []
g = [[] for _ in range(r)]
visited = [[False] * r for N in range(c)]
for i in range(r):
    g[i] = [aToIdx(x) for x in sys.stdin.readline().rstrip()]


def dfs(start,depth):
    global maximum
    if maximum == 26:
        return
    maximum = max(maximum,depth)
    for node in graph[start[0],start[1]]:
        v = g[node[0]][node[1]]
        if not visited[node[0]][node[1]] and not alpha[v]:
            alpha[v] = True
            visited[node[0]][node[1]] = True
            dfs(node,depth+1)
            visited[node[0]][node[1]] = False
            alpha[v] = False


dx = [1,-1,0,0]
dy = [0,0,1,-1]
x,y = 0,0
graph = dict()
for i in range(r):
    for j in range(c):
        temp = []
        for k in range(4):
            nx = j + dx[k]
            ny = i + dy[k]
            if nx<0 or nx>=c or ny<0 or ny >= r:
                continue
            else:
                temp.append([ny,nx])
        graph[i,j] = temp
maximum = 0
alpha = [False]*26
alpha[g[0][0]] = True
visited[0][0] = True
dfs([0,0],1)
print(maximum)