[BOJ] 1987 - 알파벳

사용 언어: Python3

문제

백준 1987

문제 풀이 핵심 아이디어

• 말은 상, 하, 좌, 우 네 가지 방향으로 이동할 수 있습니다.
• 지금까지 지나온 모든 칸에 적혀있는 알파벳과 다른 알파벳이 적힌 칸으로 이동해야 합니다.
• 행의 길이(R)와 열의 길이(C)가 20 이하이므로, 백트래킹을 이용하여 모든 경우의 수를 고려합니다.
• R = 2, C = 4일 때의 정답 예시는 다음과 같습니다.
  
  • 🌟 CAD와 같이 이동 경로를 문자열로 본다면 쉽게 풀 수 있습니다.

내 풀이

첫 번째

R, C = map(int, input().split())
M = [[x for x in input()] for _ in range(R)]

ck = [M[0][0]] # 지나온 알파벳을 담는 배열

dx, dy = [0,-1,0,1], [1,0,-1,0]
ans = -1 # 최대 칸 수
cnt = 1 # 처음 출발지


def dfs(x,y):
  global cnt
  ck.append(M[x][y])
  cnt += 1
  # dfs(cnt,x)

def move(x,y):
  for w in range(4):
    xx = x + dx[w]
    yy = y + dy[w]
    if xx < 0 or xx > R-1 or yy < 0 or yy > C-1:
      continue
    if M[xx][yy] not in ck:
      # print(M[xx][yy])
      dfs(xx,yy)

move(0,0)
ans = max(ans, cnt)
print(ans) 

다른 사람 풀이

백트래킹

R, C = map(int, input().split())
M = [[x for x in input()] for _ in range(R)]
dx, dy = [0,-1,0,1], [1,0,-1,0]

# bfs는 큐를 이용하는 방식이지만 여기서는 set을 사용
def bfs(x,y):
  global ans
  # 동일한 경우는 한 번만 계산하기 위해 set 사용
  q = set()
  q.add((x, y, M[x][y]))

  while q:
    x, y, path = q.pop()
    # 가장 긴 이동 거리를 저장
    ans = max(ans, len(path))

    for w in range(4):
      xx = x + dx[w]
      yy = y + dy[w]
      # 이동할 수 있는 위치이면서 
      if xx < 0 or xx > R-1 or yy < 0 or yy > C-1:
        continue
      # 새로운 알파벳인 경우
      if M[xx][yy] not in path:
        q.add((xx, yy, path+M[xx][yy]))

ans = 0
bfs(0,0)
print(ans)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기