Algorithm-알파벳

---

백준 1987 : 문제링크

• 문제유형 :

  • 백 트레킹

• 설명

  • 말을 상하좌우 네 가지 방향으로 이동시킨다
  • 지금까지 지나온 모든 칸에 적힌 알파벳과 다른 알파벳이 적인 칸으로 이동
  • 백 트레킹을 이용하여 다른 알파벳이 적힌 칸으로 이동하도록 한다

• 풀이

  dx = [-1, 1, 0, 0]
  dy = [0, 0, 1, -1]
  
  def bfs(x, y):
      global result
      q = set()
      q.add((x, y, array[x][y]))
  
      while q:
          x, y, step = q.pop()
          result = max(result, len(step))
  
          for i in range(4):
              nx = x + dx[i]
              ny = y + dy[i]
          
              if (0 <= nx and nx < r and 0 <= ny and ny < c 
                  and array[nx][ny] not in step)
                  q.add(nx, ny, step + array[nx][ny])
      
  r, c = map(int, input().split())
  array = []
  for _ in range(r):
      array.append(input())
  
  result = 0
  bfs(0, 0)
  print(result)