[파이썬] 백준 9019 : DSLR (골드4)

[파이썬] 백준 9019 : DSLR (골드4)

9019번: DSLR

---

문제

---

풀이

0. 방향성 생각

연산 맞춰서 구현하기

BFS로 탐색 진행하고 가장 먼저 발견했을 때 명령어 출력

 

1. 입력

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

cmd = dict(zip((0,1,2,3),('D','S','L','R')))

for _ in range(int(input())):
    start,end = map(int,input().split())
    visit = [False]*10000
    visit[start] = True
    q = deque([(start,'')])
    while q:
        x,command = q.popleft()
        if x == end:
            print(command)
            break

입력받고 루프 생기지 않게 visit 배열 만들어주고 시작

큐 뒷부분에는 명령어를 넣어준다. 처음에는 빈 문자열 '' 시작

큐에서 꺼내서 목표값 end랑 같으면 탈출

 

2. 연산 정의

        for i in range(4):
            if i==0:
                _,nx = divmod(x*2,10000)
            elif i==1:
                nx = 9999 if x==0 else x-1
            elif i==2:
                nx = str(x)
                nx = nx.rjust(4,'0')
                nx = int(nx[1:]+nx[0])
            else:
                nx = str(x)
                nx = nx.rjust(4,'0')
                nx = int(nx[-1]+nx[:3])
                
            if not visit[nx]:
                visit[nx] = True
                q.append((nx,command+cmd[i]))

D는 2배 이후에 모듈러 연산

S는 -1, 삼항연산자 사용

L,R은 문자열 rjust사용. 앞 자리수는 0으로 채워서 시프트 연산 가능하게 한다.

---

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

cmd = dict(zip((0,1,2,3),('D','S','L','R')))

for _ in range(int(input())):
    start,end = map(int,input().split())
    visit = [False]*10000
    visit[start] = True
    q = deque([(start,'')])
    while q:
        x,command = q.popleft()
        if x == end:
            print(command)
            break
        
        for i in range(4):
            if i==0:
                _,nx = divmod(x*2,10000)
            elif i==1:
                nx = 9999 if x==0 else x-1
            elif i==2:
                nx = str(x)
                nx = nx.rjust(4,'0')
                nx = int(nx[1:]+nx[0])
            else:
                nx = str(x)
                nx = nx.rjust(4,'0')
                nx = int(nx[-1]+nx[:3])
                
            if not visit[nx]:
                visit[nx] = True
                q.append((nx,command+cmd[i]))

코멘트

readline인데 readlind라 써서 틀림..