[백준 2210] 숫자판 점프

제약 사항

문제

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

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

입력

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

출력

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

예제

예제

 

---

나의 풀이

이 문제는 전형적인 DFS 문제이다.

2021.05.23 - 너비 우선 탐색(BFS, Breadth First Search) 파이썬 구현

너비 우선 탐색(BFS, Breadth First Search) 파이썬 구현

def bfs(graph, x, y, depth, num):
    depth += 1
    num += graph[x][y] # 숫자 추가
    if depth > 5:
        nums.add(num)
        return
    dx = [1, -1, 0, 0]
    dy = [0, 0, -1, 1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < 5 and 0 <= ny < 5:
            bfs(graph, nx, ny, depth, num)
            
graph = [list(input().split()) for _ in range(5)]
nums = set()

for i in range(5):
    for j in range(5):
        num = ''
        bfs(graph, i, j, 0, num)
        
print(len(nums))

graph에 5x5의 크기로 입력 받는 것은 [list(input().split()) for _ in range(5)] 한 줄로 가능하다.

nums는 가능한 숫자들을 담는 목적인데 중복을 제거하기 위해 set으로 만들었다.

이후 이중 반복문으로 25개의 서로 다른 시작점에서 BFS를 시행했다.

BFS 부분을 보면 정지 조건이 숫자가 6개가 되면 정지하는 것이기 때문에 depth라는 매개 변수로 관리를 해주었다.

그리고 숫자는 num이라는 매개 변수로 관리를 해주었다.

bfs에 들어가면 depth를 1 증가시키고 num에 현재 위치의 숫자를 추가한다. 이후 depth가 6이라면 num이 6자리이므로 nums에 추가해주고 bfs를 빠져나온다.

depth가 6보다 작다면 상, 하, 좌, 우 순으로 재귀적으로 bfs를 시행한다.

채점 결과