[백준] 1987 - 알파벳

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

1987번: 알파벳

문제 한줄 이해

- 1행 1열에서 시작해서 그래프를 탐색할 때 이미 지나온 알파벳이 없는 곳으로 이동하면서 최대 몇번 가능한지 구하기

생각난 풀이

1번째 방법: 첫번째로 현재위치에서 상하좌우 이동하기

                  두번째로 상하좌우 이동하기 전 이미 지나왔던 알파벳인지 판단하기

import sys
r,c = map(int,sys.stdin.readline().split())
graph = []

for i in range(r):
    graph.append(list(map(str,sys.stdin.readline().strip())))

def dfs(x,y,nowalph):
    global result
    if nowalph in nowlist:
        if result < len(nowlist):
            result = len(nowlist)
        return
    elif nowalph not in nowlist:
        if x-1 >= 0:
            nowlist.append(nowalph)
            dfs(x-1,y,graph[x-1][y]) # 상
            nowlist.pop()
        if x+1 < r:
            nowlist.append(nowalph)
            dfs(x+1,y,graph[x+1][y]) # 하
            nowlist.pop()
        if y-1 >=0:
            nowlist.append(nowalph)
            dfs(x,y-1,graph[x][y-1]) # 좌
            nowlist.pop()
        if y+1 < c:
            nowlist.append(nowalph)
            dfs(x,y+1,graph[x][y+1]) # 유
            nowlist.pop()
nowlist = []
result = 0
dfs(0,0,graph[0][0])
print(result)

제줄 후 시간 초과가 발생했다. 그래서 코드를 아무리 봐도 문제가 없다고 생각했지만 if 요소 in 리스트가 단순 O(1)인줄 알았는데 O(n)이였다. 물론 리스트의 길이가 길지 않겠지만 최대한 줄여보자 생각했고 코드도 간결하게 바꿔보자 생각했다.

 

import sys
r,c = map(int,sys.stdin.readline().split())
graph = []

for i in range(r):
    graph.append(list(map(str,sys.stdin.readline().strip())))

def dfs(x,y,cnt):
    global result
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if nx >= 0 and ny >= 0 and nx <r and ny<c:
            if nowlist[ord(graph[nx][ny])] == 1:
                if result < cnt:
                    result = cnt
                continue
            elif nowlist[ord(graph[nx][ny])] == 0:
                nowlist[ord(graph[nx][ny])] = 1
                dfs(nx,ny,cnt+1)
                nowlist[ord(graph[nx][ny])] = 0
#리스트에 요소가 들어있는지 판단을 0,1로 체크하기
nowlist = [0] * 123
result = 0
nowlist[ord(graph[0][0])] = 1
dx = [0,0,1,-1]
dy = [1,-1,0,0]
dfs(0,0,1)
print(result)

정답!!!!!!!!!!! 아무래도 파이썬이 많이 느린거 같다 ...