[파이썬][백준 1987][💛골드 4] 알파벳 (DFS, 백트래킹)

🧞‍♂️ 난이도

💛 골드 4

🧞‍♂️ 문제

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

🧞‍♂️ 내 풀이 ⭕

당연히 bfs 같았는데, 계속 시간초과가 발생했다 찾아보니까 백트래킹으로 푸는것 같은데,,bfs 로 가능은 한것 같다 최적화를 최적화하면?

import sys
input = sys.stdin.readline

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

def bfs():
  result=1
  queue=set([(0,0,board[0][0])])

  while queue: 
    x,y,visited=queue.pop()

    for i in range(4):
      nx, ny = x + dx[i], y + dy[i]
      if nx < 0 or nx >= r or ny < 0 or ny >= c:
        continue
      elif board[nx][ny] not in visited:
        next_visited = visited + board[nx][ny]
        queue.add((nx,ny,next_visited))
        result = max(result,len(next_visited))

  return result
  
r,c=map(int, input().split())
board=[]
for i in range(r):
  board.append(list(input()))

print(bfs())

---

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기