스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.
나머지 빈 칸을 채우는 방식은 다음과 같다.
각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.
또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.
이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.
게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.
입력
아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
출력
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.
제한
baekjoon의 백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다. 다음은 그 알고리즘의 수행 시간이다.
C++14: 80ms
Java: 292ms
PyPy3: 1172ms
예제 입력 1복사
035469278
782105609
060278135
321046897
804913506
596820413
917652080
603701952
258394760
예제 출력 1복사
135469278
782135649
469278135
321546897
874913526
596827413
917652384
643781952
258394761
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static int[][] map = null;
static int[][] zero = null;
static boolean[][] check = null;
static int zeroCnt;
public static boolean isPossible(int r, int c) {
// 행 검사
for(int i = 0; i < 9; i++) {
if(i == c) continue;
if(map[r][i] == map[r][c]) {
return false;
}
}
// 열 검사
for(int i = 0; i < 9; i++) {
if(i == r) continue;
if(map[i][c] == map[r][c]) {
return false;
}
}
// 3x3 사각형 검사
int row = r / 3 * 3;
int col = c / 3 * 3;
for(int i = row; i < row + 3; i++) {
for(int j = col; j < col + 3; j++) {
if(i == r && j == c) continue;
if(map[i][j] == map[r][c]) {
return false;
}
}
}
return true;
}
public static void dfs(int deptNow, int dept) {
if(deptNow == dept) { // 모든 0 처리 완료
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
System.exit(0);
}
int r = zero[deptNow][0];
int c = zero[deptNow][1];
for(int i = 1; i <= 9; i++) {
map[r][c] = i;
if(isPossible(r, c)) { // 새로운 칸 채울 때마다 검사해서 불필요한 재귀를 막는다.
dfs(deptNow + 1, dept);
}
map[r][c] = 0;
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
map = new int[9][9];
zero = new int[81][2];
check = new boolean[9][9];
for(int i = 0; i < 9; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < 9; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j] == 0) {
zero[zeroCnt][0] = i;
zero[zeroCnt][1] = j;
zeroCnt += 1;
}
}
}
int r = zero[0][0];
int c = zero[0][1];
for(int i = 1; i <= 9; i++) {
map[r][c] = i;
if(isPossible(r, c)) {
dfs(1, zeroCnt);
}
map[r][c] = 0;
}
}
}
바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.
암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.
새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.
입력
첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.
출력
각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.
예제 입력 1
46
atcisw
예제 출력 1
acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static StringBuilder sb = null;
static ArrayList<String> ans = null;
static char[] arr = null;
static boolean[] check = null;
static int L, C;
public static boolean isPossible() {
int consonant = 0, vowel = 0;
for(int i = 0; i < sb.length(); i++) {
char c = sb.charAt(i);
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
vowel += 1;
}else {
consonant += 1;
}
}
// 사실 입력받은 문자들은 중복되지 않는 것이 보장되기 때문에 contains()는 검사할 필요 없음
if(consonant >= 2 && vowel >= 1 && !ans.contains(sb.toString())) {
return true;
}else {
return false;
}
}
public static void dfs(int deptNow, int dept) {
if(deptNow == dept) {
if(isPossible()) {
ans.add(sb.toString());
}
return;
}
for(int i = 0; i < C; i++) {
if(!check[i] && sb.charAt(sb.length() - 1) < arr[i]) {
check[i] = true;
sb.append(arr[i]);
dfs(deptNow + 1, dept);
check[i] = false;
sb.deleteCharAt(sb.length() - 1);
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
sb = new StringBuilder();
L = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
ans = new ArrayList<>();
arr = new char[C];
check = new boolean[C];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < C; i++) {
arr[i] = st.nextToken().charAt(0);
}
Arrays.sort(arr);
for(int i = 0; i < C; i++) {
check[i] = true;
sb.append(arr[i]);
dfs(1, L);
check[i] = false;
sb.deleteCharAt(sb.length() - 1);
}
Collections.sort(ans);
for(String str : ans) {
System.out.println(str);
}
}
}
백트래킹을 사용해 모든 조합을 구한다.
단, 조합을 만드는 과정에서 문제의 제한사항을 잘 적용시켜야 한다.
(오름차순 정렬, 자음과 모음 개수 등)
char[]를 쓸까 String을 쓸까 StringBuilder를 쓸까 쓸 데 없는 고민으로 코드를 이리저리 바꿔가며 시간을 잡아먹었다.
강호는 코딩 교육을 하는 스타트업스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.
스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.
보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)
강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오. 만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력한다.
입력
첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.
출력
첫째 줄에 강호가 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력한다. 만약, 엘리베이터로 이동할 수 없을 때는 "use the stairs"를 출력한다.
예제 입력 1
1011021
예제 출력 1
6
예제 입력 2
1002110
예제 출력 2
usethestairs
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static int F, S, G, U, D, ans = -1;
static int[] map = null;
static boolean[] check = null;
public static void bfs() {
Queue<Integer> que = new ArrayDeque<>();
que.add(S);
map[S] = 0;
check[S] = true;
while(!que.isEmpty()) {
int now = que.poll();
int up = now + U;
int down = now - D;
if(up == G || down == G) { // 최단경로 찾으면 굳이 탐색 이어갈 필요 없음
ans = map[now] + 1;
return;
}
if(up <= F && !check[up]) {
que.add(up);
map[up] = map[now] + 1;
check[up] = true;
}
if(1 <= down && !check[down]) {
que.add(down);
map[down] = map[now] + 1;
check[down] = true;
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
// F, S, G, U, D
F = Integer.parseInt(st.nextToken());
S = Integer.parseInt(st.nextToken());
G = Integer.parseInt(st.nextToken());
U = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
if(S == G) { // 예외처리
System.out.println(0);
return;
}
map = new int[F + 1]; // map[idx] : idx층에 가기 위한 최소 버튼 수
check = new boolean[F + 1];
bfs();
System.out.println((ans == -1) ? "use the stairs" : ans);
}
}
전형적인 BFS를 사용한 최단경로 문제.
if(S == G) 의 예외처리에서 return을 안 넣어서 틀린 걸 멍청하게 한참 찾았다.
알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 편의상 모든 문자는 대문자라 생각하자. 예를 들어 아래와 같은 문자판을 보자.
K
A
K
T
X
E
A
S
Y
R
W
U
Z
B
Q
P
이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다. 예를 들어 K=2일 때 아래의 그림의 가운데에서는 'X' 표시된 곳으로 이동할 수 있다.
X
X
X
X
X
X
X
X
반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다.
이와 같은 문자판과 K, 그리고 하나의 영단어가 주어졌을 때, 이와 같은 영단어를 만들 수 있는 경로가 총 몇 개 존재하는지 알아내는 프로그램을 작성하시오.
위의 예에서 영단어가 BREAK인 경우에는 다음과 같이 3개의 경로가 존재한다. 앞의 수는 행 번호, 뒤의 수는 열 번호를 나타낸다.
(4, 2) (3, 2) (2, 2) (1, 2) (1, 1)
(4, 2) (3, 2) (2, 2) (1, 2) (1, 3)
(4, 2) (3, 2) (2, 2) (2, 3) (1, 3)
입력
첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다.
출력
첫째 줄에 경로의 개수를 출력한다. 이 값은 int 범위이다.
예제 입력 1
441
KAKT
XEAS
YRWU
ZBQP
BREAK
예제 출력 1
3
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static char[][] map = null;
static int[][][] dp = null;
static int[] rArr = {-1, 1, 0, 0};
static int[] cArr = {0, 0, -1, 1};
static String target = null;
static int n, m, k, ans;
public static void dfs(int r, int c, int idx, int length) {
if(idx == length - 1) { // 마지막 idx까지 도착. 문자열 완성.
dp[r][c][idx] = 1;
return;
}
if(dp[r][c][idx] != -1) { // 이미 방분한 곳이면 리턴하고 그 값 더함
return;
}
dp[r][c][idx] = 0; // 방문한 노드는 0으로 해줘야 함. -1값을 그대로 유지하면 나중에 값을 더할 때 문제가 생길 수 있다.
for(int i = 1; i <= k; i++) {
for(int j = 0; j < 4; j++) { // k가 1씩 증가할 때마다 현재 위치에서 상하좌우 1칸씩 더 검사
int nr = r + rArr[j] * i;
int nc = c + cArr[j] * i;
if(-1 < nr && nr < n && -1 < nc && nc < m) { // n행 m열 범위 체크
if(map[nr][nc] == target.charAt(idx + 1)) { // 다음 문자 일치하면 재귀
dfs(nr, nc, idx + 1, length);
dp[r][c][idx] += dp[nr][nc][idx + 1];
}
}
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
map = new char[n][m];
for(int i = 0; i < n; i++) {
String input = br.readLine();
for(int j = 0; j < m; j++) {
map[i][j] = input.charAt(j);
}
}
target = br.readLine();
dp = new int[n][m][target.length()]; // 방문하지 않은 상를 -1로 초기화해야함
for(int i = 0; i < n; i++) { // 0으로 초기화하면
for(int j = 0; j < m; j++) {
Arrays.fill(dp[i][j], -1);
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(map[i][j] == target.charAt(0)) {
dfs(i, j, 0, target.length());
ans += dp[i][j][0];
}
}
}
System.out.println(ans);
}
}
너무너무너무너무너무 어려웠고 시간도 오래 걸렸다. 결국 구글링과 오픈카톡의 도움을 받았다.
일단 처음엔 문제를 잘못 이해했다. 같은 칸을 여러 번 방문할 수 "없다"인 줄 알았는데, "있다" 였다.
이는 무작정 중복조회가 가능하다는 의미가 아니다.
예를들어, ABABA 라는 문자열을 찾는다고 할 때, 하나의 좌표 (r, c)에 있는 A를 [0], [2], [4]에 모두 사용할 수 있다는 뜻이다.
즉, 다른 인덱스의 문자를 찾는 데에 한해서 중복조회를 허용한다는 것이다.
-> (근데 결국 그게 무작정 중복조회를 허용한다는 얘긴가..? 음..?)
-> (생각해보니 같은 인덱스에 대한 중복 조회를 허용하면 경우의 수가 무한하게 나오게 될 테니 이건 애초에 말이 안 되는 소리였다.)
비록 다른 인덱스에 한해서이긴 하지만 중복조회를 허용한다는 대목에서 브루트포스로는 절대 해결할 수 없다는 것을 눈치채야한다.
map의 크기는 최대 100*100으로 10,000이고 타겟 문자열의 최대 길이는 80. 대충 생각해봐도 브루트포스는 불가능하다.
다음 인덱스의 문자와 일치하는 좌표에 대해서만 재귀를 수행한다면 그래도 시간 안에 들어올 수 있지 않을까 하는 헛된 희망을 가지고 코드를 짰으나 어림도 없었다.
시간초과에서 빠져나오기 위해 DFS에 DP를 함께 사용해야한다.
DP문제에선 항상 그렇듯이 dp 배열에 무엇을 담을 것인지가 중요하다.
-> dp[r][c][idx] == (r, c)를 idx번째 인덱스로 사용할 수 있는 정답 경우의 수
이렇게하면 문제의 요구사항대로 같은 인덱스에 대해서는 중복조회를 막으면서 다른 인덱스에 대해서만 중복조회를 허용할 수 있게 된다.
DP의 초기값을 0으로 했다가 또 문제가 발생했다.
처음에는, 어차피 if(map[nr][nc] == target.charAt(idx + 1)) 을 사용해서 다음 인덱스의 문자가 일치하는 것에 대해서만 재귀호출을 실행하니까 초기화를 0으로 하더라도 별 문제가 없을 것이라고 생각했다.
그런데 별 문제가 있다.
예를 들어, 길이가 5인 문자열을 찾아야 할 때 길이 3까지만 일치하고 그 이후로는 일치하는 문자를 찾을 수 없다면?
결국 dp[] = 0이 의미하는 바가 아래의 두 가지 경우를 모두 포함하게 되어 제대로 된 구분을 할 수 없게 된다.
1. 아직 방문하지 않음(= 초기값으로서의 의미) 2. 해당 경우에서 정답을 완성시킬 수 있는 경우의 수가 0개.
방문하지 않았으면 탐색을 진행하도록 하고, 해당 경우에서 정답을 완성시킬 수 없으면 더이상 탐색을 진행하지 않아야하는데, 초기값이 이렇게 중복적인 의미를 띄게 되면 메모이제이션이 제대로 작동하지 않게 되고.. 결과적으로 안 해도 될 탐색을 더 수행하게 돼서 시간초과가 나는 것이다.
모호성을 피하기 위해서 DP 초기값은 반드시 0이 아닌, "방문하지 않음" 만을 의미하도록 잡아야한다.
각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.
이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.
입력
첫째 줄에 세 정수 A, B, C가 주어진다.
출력
첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.
예제 입력 1
8910
예제 출력 1
128910
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Bottle {
int a;
int b;
int c;
Bottle(int a, int b, int c) {
this.a = a;
this.b = b;
this.c = c;
}
}
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static int[] mBottle; // ([0] = A, [1] = B, [2] = C) 의 용량(= 크기)
static boolean[][][] check = null; // [A][B][C]
static ArrayList<Integer> ans = null;
static Queue<Bottle> que = null;
public static void pourWater(int from, int to, int[] pBottle) { // from은 반드시 비어있지 않아야한다.
// from, to는 pBottle의 인덱스
// pBottle = {a, b, c}
int[] temp = {pBottle[0], pBottle[1], pBottle[2]};
if(temp[from] + temp[to] <= mBottle[to]) { // from의 물을 다 붓는 경우
temp[to] += temp[from];
temp[from] = 0;
}else { // to가 꽉 찰때까지만 붓는 경우
temp[from] -= mBottle[to] - temp[to]; // to의 남은 공간만큼만 붓는다.
temp[to] = mBottle[to]; // to는 꽉 차게 된다.
}
int nowA = temp[0], nowB = temp[1], nowC = temp[2];
if(!check[nowA][nowB][nowC]) {
que.add(new Bottle(nowA, nowB, nowC));
check[nowA][nowB][nowC] = true;
if(nowA == 0) ans.add(nowC); // A == 0 일 때, C값 저장
}
}
public static void bfs(int a, int b, int c) {
que = new ArrayDeque<>();
que.add(new Bottle(a, b, c));
check[a][b][c] = true;
ans.add(c);
while(!que.isEmpty()) {
Bottle bottle = que.poll();
int[] pBottle = {bottle.a, bottle.b, bottle.c};
if(pBottle[0] != 0) { // from A
if(pBottle[1] != mBottle[1]) pourWater(0, 1, pBottle);
if(pBottle[2] != mBottle[2]) pourWater(0, 2, pBottle);
}
if(pBottle[1] != 0) { // from B
if(pBottle[0] != mBottle[0]) pourWater(1, 0, pBottle);
if(pBottle[2] != mBottle[2]) pourWater(1, 2, pBottle);
}
if(pBottle[2] != 0) { // from C
if(pBottle[0] != mBottle[0]) pourWater(2, 0, pBottle);
if(pBottle[1] != mBottle[1]) pourWater(2, 1, pBottle);
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
mBottle = new int[3];
mBottle[0] = Integer.parseInt(st.nextToken());
mBottle[1] = Integer.parseInt(st.nextToken());
mBottle[2] = Integer.parseInt(st.nextToken());
check = new boolean[mBottle[0] + 1][mBottle[1] + 1][mBottle[2] + 1];
ans = new ArrayList<>();
bfs(0, 0, mBottle[2]);
Collections.sort(ans);
for(int c : ans) {
System.out.print(c + " ");
}
}
}
어려운 문제는 아닌데 구현으로 시간을 꽤 잡아먹었다.
DFS, BFS 뭘 사용하든 상관없어보인다.
노드의 개수 = 숫자 3개의 합으로 200을 만드는 모든 경우의 수
에지의 개수 = 6개 (한 물통에서 한 물통으로 물을 옮기는 경우의 수)
check[][][] 으로 8MB를 사용한다. 메모리 제한에 충분히 여유롭긴 하지만 뭔가 낭비되는 게 많은 느낌.
네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1× 10 + d2) × 10 + d3) × 10 + d4라고 하자)
D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.
위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다.
여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.
1234 →L2341 →L3412 1234 →R4123 →R3412
따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.
n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.
입력
프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.
출력
A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.
예제 입력 1
3
12343412
10001
116
예제 출력 1
LL
L
DDDD
풀이 1. (틀린코드 - 시간초과)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
class Pair {
String instruction;
String number;
Pair(String intstruction, String number) {
this.instruction = intstruction;
this.number = number;
}
}
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static boolean[] check = null;
static String ans;
public static String makeLengthFour(String str) {
int len = str.length();
String result = str;
for(int i = 0; i < len; i++) {
result = "0" + result;
}
return result;
}
public static String d(String strNum) {
int num = Integer.parseInt(strNum);
num = 2 * num % 10000;
String result = makeLengthFour(String.valueOf(num));
return result;
}
public static String s(String strNum) {
int num = Integer.parseInt(strNum);
if(num == 0) num = 9999;
else num -= 1;
String result = makeLengthFour(String.valueOf(num));
return result;
}
public static String l(String strNum) {
String temp = makeLengthFour(strNum);
String result = String.valueOf(temp.charAt(1));
result += String.valueOf(temp.charAt(2));
result += String.valueOf(temp.charAt(3));
result += String.valueOf(temp.charAt(0));
return result;
}
public static String r(String strNum) {
String temp = makeLengthFour(strNum);
String result = String.valueOf(temp.charAt(3));
result += String.valueOf(temp.charAt(0));
result += String.valueOf(temp.charAt(1));
result += String.valueOf(temp.charAt(2));
return result;
}
public static void bfs(int start, int destination) {
String strStart = String.valueOf(start);
Queue<Pair> que = new ArrayDeque<>();
que.add(new Pair("", makeLengthFour(strStart)));
check[start] = true;
while(!que.isEmpty()) {
Pair p = que.poll();
String inst = p.instruction;
String now = p.number;
String dStr = d(now), sStr = s(now), lStr = l(now), rStr = r(now);
int dNum = Integer.parseInt(dStr), sNum = Integer.parseInt(sStr), lNum = Integer.parseInt(lStr), rNum = Integer.parseInt(rStr);
if(dNum == destination) {ans = inst + "D"; return;}
if(sNum == destination) {ans = inst + "S"; return;}
if(lNum == destination) {ans = inst + "L"; return;}
if(rNum == destination) {ans = inst + "R"; return;}
if(!check[dNum]) {que.add(new Pair(inst + "D", dStr)); check[dNum] = true;}
if(!check[sNum]) {que.add(new Pair(inst + "S", sStr)); check[sNum] = true;}
if(!check[lNum]) {que.add(new Pair(inst + "L", lStr)); check[lNum] = true;}
if(!check[rNum]) {que.add(new Pair(inst + "R", rStr)); check[rNum] = true;}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
while(T-- > 0) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
check = new boolean[10000];
bfs(from, to);
System.out.println(ans);
}
}
}
String 연산을 쓸데없이 많이 사용해서 시간초과가 난 거 같다.
숫자의 길이에 대한 주의사항 때문에 일부러 makeLengthFour() 같은 것도 만들고 이것저것 신경을 썼는데.. 오히려 그게 시간초과로 발목을 잡았다.
풀이 2. (정답코드)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static boolean[] check = null;
static String[] instructions = null;
static String ans;
public static void bfs(int start, int destination) {
Queue<Integer> que = new ArrayDeque<>();
que.add(start);
check[start] = true;
while(!que.isEmpty()) {
int now = que.poll();
int D = 2 * now % 10000;
int S = (now-1 == -1) ? 9999 : now-1;
int L = (now % 1000) * 10 + (now / 1000);
int R = (now / 10) + (now % 10) * 1000;
if(D == destination) { ans = instructions[now] + "D"; return; }
if(S == destination) { ans = instructions[now] + "S"; return; }
if(L == destination) { ans = instructions[now] + "L"; return; }
if(R == destination) { ans = instructions[now] + "R"; return; }
if(!check[D]) { que.add(D); check[D] = true; instructions[D] = instructions[now] + "D"; }
if(!check[S]) { que.add(S); check[S] = true; instructions[S] = instructions[now] + "S"; }
if(!check[L]) { que.add(L); check[L] = true; instructions[L] = instructions[now] + "L"; }
if(!check[R]) { que.add(R); check[R] = true; instructions[R] = instructions[now] + "R"; }
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
while(T-- > 0) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
check = new boolean[10000];
instructions = new String[10000];
Arrays.fill(instructions, "");
bfs(from, to);
System.out.println(ans);
}
}
}
애초부터 String을 그렇게 남발할 필요도 없었고 D, S, L, R 각 명령을 함수로 만들 필요도 없었다.
