[백준] 1987 파이썬(python) : 알파벳 - (★)

1987번 : 알파벳

 

 

pypy3로 제출해서 간신히 통과했다. 왜인지 모르겠지만 sys.setrecursionlimit(10**9)를 해줬을때는 틀렸지만 이 코드를 지워주니까 통과했다.

 

import sys
r, c = map(int, sys.stdin.readline().split())
graph = [ list(sys.stdin.readline().rstrip()) for _ in range(r) ]
tmp = set() #1
cnt = 1 #2
dx = [ 0, 0, -1, 1 ]
dy = [ -1, 1, 0, 0 ]
def dfs(x, y, count):
    global cnt
    cnt = max(count, cnt) #3
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < r and 0 <= ny < c:
            if graph[nx][ny] not in tmp:
                tmp.add(graph[nx][ny]) #4
                dfs(nx, ny, count+1) #5
                tmp.remove(graph[nx][ny]) #6
tmp.add(graph[0][0]) #7
dfs(0, 0, cnt)
print(cnt)

 

#1 : 중복되는 알파벳들은 정리해주기 위해 set() 처리

#2 : 맨 처음 방문횟수는 1

#3 : 변수를 2개 만들지 않고 최대값을 구할 수 있는 방법

#4 : 방문처리

#6 : 백트래킹이므로 방문처리 제거

#7 : 맨 처음위치 방문처리 후 dfs()실행

 

파이썬은 느리기 때문에 백준에서 보너스시간을 준다고 한다. 이 문제는 제한시간이 2초인데 1000ms = 1초이므로 7932ms가 나온 나의 코드는 오답이어야 하지만 Python3와 pypy3는 (시간제한 * 3 + 2)만큼의 보너스 시간을 준다고 한다.

그래서 2초짜리 문제를 2*3+2 = 8초까지 늘려주고 통과할 수 있는것이다.

 

 

bfs를 사용한 풀이) - pypy3제출

계속 dfs는 시간초과나서 bfs를 찾았다

import sys
r, c = map(int, sys.stdin.readline().split())
graph = [ sys.stdin.readline().rstrip() for _ in range(r) ]
cnt = 1 #1
dx = [ 0, 0, -1, 1 ]
dy = [ -1, 1, 0, 0 ]

def bfs():
    global cnt
    q = set() #2
    q.add((0, 0, graph[0][0])) #3
    while q:
        x, y, z = q.pop() #4
        cnt = max(cnt, len(z)) #5
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < r and 0 <= ny < c and graph[nx][ny] not in z: #6
                q.add((nx, ny, z+graph[nx][ny])) #7
bfs()
print(cnt)

 

#1 : 첫번째 위치는 방문이니까

#2 : bfs의 큐를 set으로 사용

#3 : 첫 시작 위치와 그 위치의 문자를 입력

#4 : 위치와 위치의 값을 꺼내서

#5 : z는 문자열이니까 문자열의 길이의 최대값을 갱신

#6 : 방향벡터로 4방향을 돌리는데 범위 안에 들어가고 문자열 z안에 새로운 문자가 안들어가는 경우

#7 : 위치와 함께 새로운 문자를 문자열 뒤에 추가해서 set에 넣어줌

 

시간초과를 막기위해서는 중복 방지를 자동으로 해주는 set을 사용해야 한다. 일반적인 리스트로 생성하고 graph[nx][ny] not in list를 사용하면 70퍼센트 쯤에서 시간초과가 나온다.