Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

27. 동적 계획법과 최단거리 역추적

지금까지는 최솟값, 최댓값, 최단거리만 찾았습니다. 이번에는 실제 최적해와 최단경로를 찾아 봅시다.

Java / Python

7. DSLR

9019번

조금 더 복잡한 BFS 문제

이번 문제는 BFS를 활용해서, D, S, L, R 명령을 하나하나 수행해주며 해당 값을 찾는 문제입니다.

• Java

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
		StringTokenizer st;
        
		int T = Integer.parseInt(br.readLine());       
        
		while(T-- > 0){
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			
			String[] cmd = new String[10000]; // 정답 담는곳
			boolean[] visit = new boolean[10000]; // BFS 탐색의 방문 여부 체크
			Queue<Integer> queue = new LinkedList<>();
			
			visit[A] = true;
			queue.add(A);
			Arrays.fill(cmd, "");
			
			while(!queue.isEmpty() && !visit[B]) {
				int now = queue.poll();
				int D = (2 * now) % 10000;
				int S = (now == 0) ? 9999 : now-1 ;
				int L = (now % 1000) * 10 + now/1000;
				int R = (now % 10) * 1000 + now/10;    
				
				if(!visit[D]) {
					queue.add(D);
					visit[D] = true;
					cmd[D] = cmd[now]+"D";
				}
				if(!visit[S]) {
					queue.add(S);
					visit[S] = true;
					cmd[S] = cmd[now]+"S";
				}
				if(!visit[L]) {
					queue.add(L);
					visit[L] = true;
					cmd[L] = cmd[now]+"L";
				}
				if(!visit[R]) {
					queue.add(R);
					visit[R] = true;
					cmd[R] = cmd[now]+"R";
				}
			}
			bw.write(cmd[B] + "\n");
		}
		bw.flush();
		br.close();
		bw.close();
	}
}

• Python

시간 초과 때문에 Pypy3로 제출했습니다..!

from collections import deque
import sys
input = sys.stdin.readline

def bfs():
    que = deque()
    que.append([a, ""])
    while que:
        num, result = que.popleft()
        dn = (num * 2) % 10000
        sn = num - 1 if num != 0 else 9999
        ln = int(num % 1000 * 10 + num / 1000)
        rn = int(num % 10 * 1000 + num // 10)
        
        if dn == b: return result + "D"
        elif cmd[dn] == 0:
            cmd[dn] = 1
            que.append([dn, result + "D"])

        if sn == b: return result + "S"
        elif cmd[sn] == 0:
            cmd[sn] = 1
            que.append([sn, result + "S"])

        if ln == b: return result + "L"
        elif cmd[ln] == 0:
            cmd[ln] = 1
            que.append([ln, result + "L"])

        if rn == b: return result + "R"
        elif cmd[rn] == 0:
            cmd[rn] = 1
            que.append([rn, result + "R"])
            
tc = int(input())
for i in range(tc):
    a, b = map(int, input().split())
    cmd = [0 for i in range(10000)]
    print(bfs())