[백준] 2210번 숫자판 점프 파이썬

DFS 유형의 문제를 풀어보았다.

 

2210번 숫자판 점프 풀이

#솔루션

board = [] # 입력 받는 숫자판
result = [] # 완성된 여섯 자리 숫자들

# 숫자판 입력
for _ in range(5):
  line = list(map(str, input().split()))
  board.append(line)
  
# 상,하,좌,우 방향
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y, num):
  if len(num) == 6: # 6자리의 숫자가 완성되면
    if num not in result: # 중복이 있는지 확인해서 없으면
      result.append(num) # 추가
    return

  # 상, 하, 좌, 우 이동
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]

# 숫자판의 범위를 벗어나는지 확인
    if nx < 0 or nx >= 5 or ny < 0 or ny >= 5:
      continue
    else:
      # 이동한 곳의 숫자 1개를 연결
      dfs(nx, ny, num + board[nx][ny])

# 5번씩 이동하여 숫자 만들기
for i in range(5):
  for j in range(5):
    dfs(i, j, board[i][j])

print(len(result)) # 총 완성된 숫자들의 개수 출력

board에 숫자들을 입력받아 숫자판을 만들었다. 5X5의 숫자판에서 5번 이동을 하여 6자리의 숫자들을 만들어서 중복 없이 완성된 숫자들의 개수를 구해야 한다.

for 문 2개를 사용해서 숫자판에 있는 전체 25개의 숫자들 각각(board[i][j])에서 시작을 한다. dfs 함수에서 6자리의 숫자가 완성된다면 그동안의 완성된 숫자들(result) 중에서 중복을 확인 한 후 중복이 없다면 추가를 해줄 수 있다. 그러나 아직 6자리의 숫자가 완성되지 않았다면 x와 y의 위치에서 dx와 dy만큼 이동하여 상하좌우의 위치(nx, ny)를 얻은 후 해당 위치가 숫자판의 범위를 벗어나버리면 continue를 사용해서 해당 경우는 무시하고, 벗어나지 않는다면 현 숫자(num)에 이동하여 얻은 숫자(board[nx][ny])를 연결한다.

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

2210번: 숫자판 점프