[항해99 취업 리부트 코스 학습일지] 백준 1987

https://www.acmicpc.net/problem/1987
오늘 이 문제 풀다가 멘탈이 나갔다. 처음에 BFS로 접근했는데 나는 BFS를 만들 때 que에 넣자마자 visited 처리를 했는데 예제 3번에서 막혔다. 그래서 DFS로 접근했는데 시간초과가 났다. 다른 문제 푼 분의 코드를 참고해서 거의 비슷하게 풀었는데도 계속 시간초과가 났다.

r, c = map(int, input().split())

board = [input() for _ in range(r)]

visited = set()

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

ans = 0

def dfs(y, x, count):
  global ans

  ans = max(ans, count)

  for d in range(4):
    ny = y + dy[d]
    nx = x + dx[d]

    if 0 <= ny < r and 0 <= nx < c and board[ny][nx] not in visited:
      visited.add(board[ny][nx])
      dfs(ny, nx, count + 1)
      visited.remove(board[ny][nx])

visited.add(board[0][0])
dfs(0, 0, 1)

print(ans)

달랐던 한 부분이 있는데 처음에 input을 받을 때 어차피 index로만 접근하기에 스트링 그대로 뒀는데 찾아보니까 파이썬에서는 string이 list보다 접근하거나 할 때 시간이 더 오래 걸린다고 하더라.

import sys

input = sys.stdin.readline

r, c = map(int, input().strip().split())
board = [list(input().strip()) for _ in range(r)]
visited = set()

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

ans = 0

def dfs(y, x, count):
  global ans
  ans = max(ans, count)
  for d in range(4):
    ny = y + dy[d]
    nx = x + dx[d]

    if 0 <= ny < r and 0 <= nx < c and board[ny][nx] not in visited:
      visited.add(board[ny][nx])
      dfs(ny, nx, count + 1)
      visited.remove(board[ny][nx])

visited.add(board[0][0])
dfs(0, 0, 1)
print(ans)

근데 그렇게 해도 한 2트만에 성공한 것 같다. 여러 억까와 string 접근으로 인해 실패한 그런 문제였다.
일단 앞으로 스트링 처리하는 문제가 나오면 일단 리스트로 변환하고 풀 것 같다.