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

숨·2024년 8월 7일

코테

알고리즘 문제 풀이

목록 보기

43/105

📌 문제 : 백준 2210번

📌 문제 탐색하기

digit : 다섯 개의 줄에 입력받은 다섯 개의 각 정수 ( $0 ≤ digit ≤ 9$ )

✅ 입력 조건
1. 5번 반복해 5개의 정수 digit 입력
✅ 출력 조건
1. 만들 수 있는 서로 다른 여섯 자리의 수들의 개수 출력

5×5 숫자판의 임의의 위치에서 시작해서 아래와 같은 조건으로 만든 서로 다른 6자리 숫자들의 개수를 구하는 문제이다.

인접한 4가지 방향(상하좌우)으로 5번 이동
시작부터 5번 이동한 칸에 적힌 6개의 숫자를 차례로 붙여 6자리 수 만듦
이미 이동한 칸에 다시 이동 가능
중복 없는 서로 다른 여섯 자리 수들의 개수 출력

BFS로 인접한 칸들을 이동하도록 구현한다.

큐를 활용해 시작점부터 탐색을 시작한다
- 숫자판 전체를 돌 것 → 실행 시 이중 for문 사용
- 시작점에 적힌 숫자에 이동한 칸의 숫자들을 문자열의 + 연산으로 합쳐줌
6개의 숫자를 얻으면 그 수를 집합에 저장한다.
현재 위치에서 4가지 방향으로 이동했을 때, 5×5 범위 내에 있는지 확인하면서 탐색하도록 한다.
큐가 빌 때까지 현재 위치, 현재까지 만들어진 숫자를 append, pop한다.

중복 없는 서로 다른 여섯 자리 수들의 개수를 구해야 하므로
set() 자료형으로 정의한 집합에 만든 6자리 수를 저장해 중복값을 하나만 저장하도록 구현한다.

가능한 시간복잡도

전체 숫자판을 도는 이중 for문 → $O(5^2) = O(25)$
4개의 방향으로 최대 5번 이동하는 bfs → $O(4^5) = O(1024)$

최종 시간복잡도
최악의 경우 $O(25 * 1024) = O(25600)$ 이다.
이는 2초 내에 연산이 가능하다.

알고리즘 선택

BFS로 전체 숫자판을 돌면서 만들 수 있는 모든 6자리 수를 구하고,
set() 자료형으로 중복값 제거하기

📌 코드 설계하기

bfs 구현
5번 반복해 digit 입력
4가지 이동 방향 정의
만든 6자리 숫자 저장할 집합 초기화
전체 숫자판을 돌면서 BFS 수행
결과 출력

📌 시도 회차 수정 사항

1회차

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline


# bfs 구현
def bfs(start_x, start_y):
    # 큐 초기화
    queue = deque([(start_x, start_y, digits[start_x][start_y])])
    # 큐가 빌 때까지
    while queue:
        x, y, num = queue.popleft()

        if len(num) == 6:
            new_nums.add(num)
            continue

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < 5 and 0 <= ny < 5:
                queue.append((nx, ny, num + digits[nx][ny]))


# 숫자 입력 리스트 초기화
digits = []

# 5번 반복해 digit 입력
for _ in range(5):
    digits.append(list(input().rstrip().split()))

# 이동 방향 정의
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# 만든 숫자 저장할 집합 초기화
new_nums = set()

# 숫자판 전체 돌면서 BFS 수행
for i in range(5):
    for j in range(5):
        bfs(i, j)

# 결과 출력
print(len(new_nums))

결과

📌 회고

# 첫번째 : 원래 이용한 방법
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# 이동시키는 방법
for i in range(4):
	nx, ny = x + dx[i], y + dy[i]


# 두번째 : 튜플 리스트로 방향 한번에 정의
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# 이동시키는 방법
for dx, dy in directions:
	nx, ny = x + dx, y + dy