[백준] # 2210. 숫자판 점프 (파이썬)

문제 링크

 

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

2210번: 숫자판 점프

 

문제 내용

 

5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다.

숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하시오.

 

입력

 

다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다.

 

출력

 

첫째 줄에 만들 수 있는 수들의 개수를 출력한다.

 

IDEA

 

BFS로 탐색하면서 새로운 여섯 자릿수를 result 배열에 저장한다. 탐색이 끝난 후 result의 개수를 출력한다.

 

CODE

 

# 2210. 숫자판 점프 - 실버2
# bfs로 접근
from collections import deque
numbers = [list(input().split()) for _ in range(5)]
result = []  # 만든 여섯자리 수 저장
dx, dy = (1,-1,0,0),(0,0,1,-1)
def bfs(m,n):
    q = deque([(m,n,"")])
    while q:
        x,y,num = q.popleft()
        if len(num) == 6:
            if num not in result:   # 중복 고려
                result.append(num)
            continue
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < 5 and 0 <= ny < 5:
                q.append((nx,ny,num+numbers[nx][ny]))
for i in range(5):
    for j in range(5):
        bfs(i,j)
print(len(result))

 

사용 알고리즘

 

BFS

 

풀이 평

 

단순 BFS문제