728x90
문제 요약
네 개의 명령어 D, S, L, R 가 있는 계산기
두 정수 A, B가 주어졌을 때, A를 B로 바꾸는 최소한의 명령어 생성
-> BFS
BFS라는 건 어렵지 않게 생각해낼 수 있었는데.. 이 문제에서 가장 어려웠던 점은 시간 초과였다.
시간 초과 풀이
from collections import deque
def D(n):
return (2 * n) % 10000
def S(n):
return n - 1 if n != 0 else 9999
def L(n):
n = f"{n:04}" # 네 자릿수로 맞추기
return int(n[1:] + n[0])
def R(n):
n = f"{n:04}" # 네 자릿수로 맞추기
return int(n[-1] + n[:-1])
def bfs(a, b):
queue = deque([(a, "")]) # 초기 상태와 명령어 나열
visited = set([a]) # 방문한 상태 저장
while queue:
current, commands = queue.popleft()
if current == b:
return commands
# 다음 상태 탐색
for next_state, command in [(D(current), "D"), (S(current), "S"), (L(current), "L"), (R(current), "R")]:
if next_state not in visited:
visited.add(next_state)
queue.append((next_state, commands + command))
t = int(input())
for _ in range(t):
a, b = map(int, input().split())
print(bfs(a, b))이 풀이가 틀린 이유는 'L'과 'R' 연산에서, 문자열 변환을 사용했기 때문이었다.
정답 풀이 (pypy3)
from collections import deque
import sys
input = sys.stdin.readline
def D(n):
return (2 * n) % 10000
def S(n):
return n - 1 if n != 0 else 9999
def L(n):
return (n % 1000) * 10 + n // 1000
def R(n):
return (n // 10) + (n % 10) * 1000
def bfs(a, b):
queue = deque([(a, "")])
visited = set()
visited.add(a)
while queue:
cur, commands = queue.popleft()
if cur == b:
return commands
for next_state, command in [(D(cur), "D"), (S(cur), "S"), (L(cur), "L"), (R(cur), "R")]:
if next_state not in visited:
visited.add(next_state)
queue.append((next_state, commands + command))
t = int(input().strip())
results = []
for _ in range(t):
a, b = map(int, input().split())
results.append(bfs(a, b))
print('\n'.join(results))
문자열 변환 vs 정수 연산
def L(n):
n = f"{n:04}" # 네 자릿수로 맞추기
return int(n[1:] + n[0])
def R(n):
n = f"{n:04}" # 네 자릿수로 맞추기
return int(n[-1] + n[:-1])이 코드를 봐보자. L연산의 예시로 1234를 하면
숫자 1234를 문자열로 변환 -> 첫 번째 문자를 제외하고 나머지 문자열 '234' -> 첫번째 문자열을 끝에 붙임 '2341' -> 문자열을 다시 정수로 변환 '2341' 이러한 과정을 거치게 된다.
def L(n):
return (n % 1000) * 10 + n // 1000
문자열 연산은 정수 -> 문자열 -> 슬라이싱 -> 문자열 -> 정수를 하는 반면,
정수 연산은 그저 정수 연산 뿐이다.
방문 확인 방식 - 리스트 vs 사전
set은 평균적으로 O(1)이 걸리지만, 최악의 경우 O(n) 시간이 걸린다.
한편 list의 인덱스 접근은 항상 O(1) 시간이 걸린다.
이 둘은 풀이의 정답을 결정짓는 요소는 아니었지만, 방문 확인 방식만 바꾸어 확인해보았을 때 리스트를 사용한 풀이가 더 빠름을 확인할 수 있었다.
visited = [False] * 10000 # 리스트 초기화
# 상태를 방문했는지 확인하는 부분
if not visited[next_state]:
visited[next_state] = True
| list | set | |
| 인덱스 접근 | O(1) | x |
| 탐색 (in 연산) | O(n) | 평균적으로 O(1), 최악의 경우 O(n) |
| 추가 | O(1) (평균적으로, 끝에 추가할 때) | 평균적으로 O(1), 최악의 경우 O(n) |
| 삭제 | O(n)(특정 위치에서 삭제할 때) | 평균적으로 O(1), 최악의 경우 O(n) |
set에서 최악의 경우, 모든 요소가 같은 해시 값을 가질 때 O(n) 시간이 걸릴 수 있다.
(참고) Python3로 통과하려면? - 양방향 BFS
제출된 python3 정답코드를 참고하니,
최대한 미리 연산하고, 양방향 BFS를 통해 시간을 단축하고 있었다.
728x90
