이번에 풀어본 문제는
백준 15684번 사다리 조작 입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N,M,H;
static int answer = -1;
static int [][] map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
map = new int[H+1][N+1];
for(int i = 0; i < M; ++i)
{
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
map[x][y] = 1;
map[x][y+1] = -1;
}
for(int i = 0; i < 4; ++i)
{
dfs(0,i);
}
System.out.print(answer);
}
static void dfs(int cnt, int dest)
{
if(cnt == dest)
{
if(play())
{
System.out.print(dest);
System.exit(0);
}
return;
}
for(int i = 1; i <= H; ++i) // 1 5
{
for(int j = 1; j < N; ++j)
{
if(map[i][j] != 0 || map[i][j+1] > 0) continue;
map[i][j] = 1;
map[i][j+1] = -1;
dfs(cnt+1,dest);
map[i][j] = 0;
map[i][j+1] = 0;
}
}
}
static boolean play()
{
boolean res = true;
for(int i = 1; i <= N; ++i)
{
int cur_x = 1;
int cur_y = i;
while(cur_x < H+1)
{
if(map[cur_x][cur_y] > 0)
{
cur_y++;
}
else if(map[cur_x][cur_y] < 0)
{
cur_y--;
}
cur_x++;
}
if(cur_y != i)
{
res = false;
break;
}
}
return res;
}
}
사다리 게임입니다.
i번에서 출발하여 i번으로 다시 돌아오게하는 사다리게임을 완성하려고 할 때, 추가적으로 배치해야하는 사다리 갯수의 최솟값을 구하는 문제입니다.
먼저 연결된 사다리는 배열의 좌표에서 우측으로 연결된 선일경우 1, 좌측일경우 -1로 정의했습니다. 쉽게말해 배열의 각 인덱스에서 -1을 만나면 왼쪽으로 이동 ,1을만나면 오른쪽 이동합니다. 이후는 -1,0,1 공통으로 아래로 하강합니다.
문제의 조건에 따라 3개를 초과하거나 방법이 없는경우 -1을 출력해야하기 때문에, dfs를 호출할때 새로 생성할 사다리의 갯수를 최대 3개까지로 하여 반복문을 구성했으며, 3개 이전에 사다리를 완성하면 값을 출력한 후 프로그램을 종료하도록 설계했습니다.
사다리를 3개 추가함에도 결과를 얻어내지 못한다면 answer은 초기값인 -1로 유지되므로 결과는 -1이 출력됩니다.
모든 경우의 수를 고려해야하는 문제이기 때문에 dfs 재귀함수를 통해 경우의 수를 조합했고, dest == cnt 일때, play() 함수를 통해 현재 상태에서 완료조건을 충족하는지 여부를 확인해주면 됩니다.
사다리를 배열로 구현하는게 조금 헷갈렸던 것 같습니다. 다양한 문제에도 당황하지 않을 수 있도록 더 많은 문제를 풀어봐야겠어요!