[백준] 1987번(알파벳)

백준 1987번

✔️ 문제 풀이

최종 제출 코드

r, c = map(int, input().split())
array = [input() for i in range(r)]

dx = [0,0,1,-1]
dy = [-1,1,0,0]
visited = [0]*26
visited[ord(array[0][0])-65] = 1
count = 0

def dfs(x, y, cnt):

  global count
  count = max(count, cnt)
  
  for i in range(4):
    if x+dx[i] < 0 or x+dx[i] >= c or y+dy[i] <0 or y+dy[i] >= r:
      continue
    
    element = ord(array[y+dy[i]][x+dx[i]])-65
    if not visited[element]:
      visited[element] = 1
      dfs(x+dx[i], y+dy[i], cnt+1)
      visited[element] = 0
      
dfs(0,0,1)
print(count)

◾ bfs 활용(시간초과)

• 문제의 로직 자체는 간단하나 시간초과로 통과가 안됨

.

◾ dfs 활용

• Python3으로는 시간초과로 통과가 안됨
• PyPy3로만 통과
• visited를 딕셔너리로 바꾸어 구현해봤으나 오히려 시간이 더 오래 걸림

✔️ 다른 풀이

참고 코드

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)

코드출처

◾ set을 활용한 bfs 풀이

• 일반적으로 넓이 우선 탐색에서 사용하는 큐는 deque로 구현하는데 여기서는 set로 구현
• 자료 탐색 시 deque는 O(n)의 시간복잡도, set은 O(1)의 시간복잡도
• 게다가 set은 무작위로 pop하기 때문에 pop의 시간복잡도는 O(1)
• visited를 공유하며 최단거리를 구하는 방식이 아니라, 현재 탐색 중인 케이스가 지나온 경로를 원소로 가지며 탐색하기 때문에 무작위로 pop해도 상관 없다
• 이렇게 되면 이 문제에서 deque이 가지는 메리트가 전혀 없기 때문에 deque를 사용할 필요가 없음

◾ 메모리, 시간

• 위의 방식이 dfs보다 메모리와 시간 모두 1/3 수준으로 절약된다.