BOJ(알파벳)(1987)

작성일 | In

알파벳 1987

  • 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다.
  • 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸(1행 1열)에는 말이 놓여 있다.
  • 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있다.
  • 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

  • 좌측 상단에서 시작해서 말이 최대한 몇 칸을 지날 수 있는지를 구하는 문제.

  • 인접한 네칸. -> 다이나믹이나 다른 방법을 푸는 건 불가능
  • 백트래킹으로 푸는게 일반적이다.
  • go (board,check,x,y,cnt)
  • board: 보드
  • check : 방문한 알파벳
  • x,y: 현재위치

  • cnt : 방문한 칸 수

  • 새로운 칸 nx,ny로 이동할 경우,
    • go(board,check,x,y,cnt+1)
    • 이 때, check는 변경해 줘야함
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def go(board, check, x, y):
    n = len(board)
    m = len(board[0])
    ans = 0
    for k in range(4):
        nx, ny = x+dx[k], y+dy[k]
        if 0 <= nx < n and 0 <= ny < m:
            ch = ord(board[nx][ny])-ord('A')
            if check[ch] == False:
                check[ch] = True
                temp = go(board, check, nx, ny)
                if ans < temp:
                    ans = temp
                check[ch] = False
    return ans+1

n,m = map(int,input().split())
board = [input() for _ in range(n)]
check = [False]*26
check[ord(board[0][0])-ord('A')] = True
print(go(board,check,0,0))

참고자료 codeplus

0%