[BOJ] 백준 1987 알파벳

태환·2024년 2월 27일
0

Coding Test

목록 보기
90/151
post-custom-banner

📌 [BOJ] 백준 1987 알파벳

📖 문제

📖 예제

📖 풀이

import sys
input = sys.stdin.readline

R, C = map(int, input().split())

graph = [list(input().strip()) for _ in range(R)]
alpha = set()

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

ans = 0

def DFS(x,y,count):
  global ans
  ans = max(ans, count)
  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 alpha:
      alpha.add(graph[nx][ny])
      DFS(nx,ny,count+1)
      alpha.remove(graph[nx][ny])


alpha.add(graph[0][0])
DFS(0,0,1)
print(ans)

지나온 길의 알파벳을 저장할 집합을 따로 만들어 DFS를 수행하고 cnt를 올려가며 조건을 만족하는 최대값을 ans에 갱신한다.
필수적으로 pypy3 파일로 제출해야하며, 채점 시 이유 모를 시간 초과가 지속적으로 발생한다. . .

profile
연세대학교 컴퓨터과학과 석사 과정
post-custom-banner

0개의 댓글