[백준] 1987 알파벳

1. 문제

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

1987번: 알파벳

 

2. 풀이

만약 누군가 이걸보신다면 제것도 pypy3로 통과해서 크게 도움되지 않을 수 있습니다 ㅠㅜ

 

이문제는,, 뭐가 문제인지 모르겠는데 질문게시판 사람들 말로는

dx, dy 좌표 차이로

dfs 내 for문 반복시 zip, enumerate, 4 이런거 차이로도 통과여부가 갈린다 이런말이 있어서

뭐가 문제인지,, 잘 모르겟네요,,

 

일단 코드 자체는 맞다고 생각합니다.

 

1. borad라고 우선 만들고, 각 칸에 알파벳을 넣습니다.

2. 여타 문제와 다를거 없이 백트래킹 하면서 여기지났네, 안지났네 표시하면서 최대 이동거리를 업데이트 합니다.

3. 여기서 visited로 이동여부를 확인합니다,,

 

## code ##

import sys, collections

n, m = map(int, sys.stdin.readline().split())
board = [[0 for x in range(m)] for x in range(n)]

for i in range(n):
    temp = sys.stdin.readline()
    for k in range(m):
        board[i][k] = temp[k]

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

def bt(visited, cx, cy, cnt):
    global max_move
    for i in range(4):
        mx, my = cx + dx[i], cy + dy[i]
        if 0 <= mx < n and 0 <= my < m and not visited[board[mx][my]]:
            visited[board[mx][my]] = True
            bt(visited, mx, my, cnt + 1)
            visited[board[mx][my]] = False
    max_move = max(max_move, cnt)

visited = collections.defaultdict(bool)
visited[board[0][0]] = True

bt(visited, 0, 0, 1)
print(max_move)