[백준 1987] 알파벳 - python (solved.ac - 골드 4)

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

1987번: 알파벳

풀이

문제를 보았을때 알수있는 힌트

문제를 통해서 그래프 문제라는 것을 알수있었다. 또한 bfs,dfs를 통해서 전진하며 카운트를 하는 문제이고, 다시 돌아오는 경우(백트레킹)를 대비하며 풀어야하는 문제이다.

이때 추가적으로 같은 알파벳이 나오는 경우 패스하면 되는 문제이다.

뭔가 접근할때 dfs를 풀면 쉽게 풀리겠다 싶어서 풀었는데 시간 초과가 계속 났다.

pypy3로 넘어가니 조금 되는가 싶었는데 역시 시간초과가 나서 다른 사람들의 코드를 확인해봤다.

결과적으로는 비슷했지만 하나 다른 점이 있었다. set 함수를 사용한 것이다.

알파벳을 담는 부분을 set으로 변경하니 통과했다.

이것의 관련되어서 찾아보았는데 list 보다 set의 속도가 더 빠르다는 것을 알수있었다.

다음에 if a in b 이런식의 문제가 있다면 b는 set으로 두고 풀어야 할듯하다.

 

import sys

nx=[0,0,1,-1]
ny=[1,-1,0,0]

def dfs(x,y,count):
    global result
    result= max(result,count)
    for i in range(4):
        dx= x+nx[i]
        dy= y+ny[i]
        if -1<dx<r and -1<dy<c and not graph[dx][dy] in alphabet:
            alphabet.add(graph[dx][dy])
            dfs(dx,dy,count+1)
            alphabet.remove(graph[dx][dy])

input= sys.stdin.readline

r,c = map(int,input().split())
graph=[]
alphabet=set()
result=0
for i in range(r):
    temp=list(input().strip())
    graph.append(temp)
# print(graph)
alphabet.add(graph[0][0])
dfs(0,0,1)
print(result)

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon1987.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리