1987 백준 알파벳 파이썬 (DFS & BFS)

  누구나 그럴싸한 계획은 있다. 코드를 제출할 때 까지

솔직히 처음에 봤을때 문제 풀이 방법이 금방 떠올라서 개꿀 문제인 줄 알았다. 

근데 막상 코드를 작성하고 보니 시간초과가 났고, 내동댕이쳐진 코드를 주섬주섬 주워서 다시 수선했더니 메모리 초과가 났다. 문제 내용에 비해 정답비율이 좀 낮아서 의아했는데 통과시키기 어려웠 같다. 

결국 통과시킨 BFS / DFS풀이 두 가지 방법이 있는데, DFS의 경우 pypy로만통과 시킬 수 있었고, BFS는 원래 사용했던 자료구조인deque가 아니라 set이라는 자료구조를 사용했다. 자료 탐색시 set의 경우 시간복잡도가 O(1)이고, deque는 O(N)이다. 이 부분에서 차이가 있었다.

 

1. 시간초과 BFS 풀이

import sys 
from collections import deque

input=sys.stdin.readline
R,C = map(int, input().split())
arr=[list(input()) for _ in range(R)]   # 알파벳 arr받고
dx=[1,-1,0,0] #방향전환
dy=[0,0,1,-1]
answer=1
def bfs(x,y):
    global answer
    queue=deque()
    queue.append([x,y,arr[x][y]])    #시작점, 
    while queue:
        x,y,ans=queue.popleft()
        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 and arr[nx][ny] not in ans:  ## not in ans 이 문법에서 속도 deque >> set 임.. set O(1) deque O(n) 
                queue.append([nx,ny,ans+arr[nx][ny]])
                answer=max(answer,len(ans)+1)
                
bfs(0,0)
print(answer)

2. 자료구조를 set으로 변경한 BFS풀이

### BFS set
import sys

R, C = map(int, sys.stdin.readline().split())
board = [list(sys.stdin.readline().strip()) for _ in range(R)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
answer = 1
def BFS(x, y):
    global answer
    q = set([(x, y, board[x][y])])
    while q:
        x, y, ans = q.pop()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if ((0 <= nx < R) and (0 <= ny < C)) and (board[nx][ny] not in ans):
                q.add((nx,ny,ans + board[nx][ny]))
                answer = max(answer, len(ans)+1)

BFS(0, 0)
print(answer)

3. DFS 풀이 pypy3 로만 통과

import sys 
from collections import deque
input=sys.stdin.readline
R,C = map(int, input().split())
arr=[list(input()) for _ in range(R)]
check=[0]*(26)

dx=[1,-1,0,0]
dy=[0,0,1,-1]
maxi=0

def dfs(x,y,cnt):
    global maxi
    maxi=max(cnt,maxi)
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if nx<R and ny<C and nx>=0 and ny>=0 and check[ord(arr[nx][ny])-65]==0:
            check[ord(arr[nx][ny])-65]=1
            ncnt=cnt+1
            dfs(nx,ny,ncnt)
            check[ord(arr[nx][ny])-65]=0

check[ord(arr[0][0])-65]=1
dfs(0,0,1)

print(maxi)

 

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

1987번: 알파벳