티스토리 뷰
https://www.acmicpc.net/problem/15684
문제
사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.
초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.
위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.
사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.
위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다. 아래 두 그림은 1번과 2번이 어떻게 이동했는지 나타내는 그림이다.
1번 세로선 | 2번 세로선 |
사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.
코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
private static int n, m, h, answer;
private static int[][] map;
private static boolean finish = false;
public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
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());
if (m == 0) {
bw.write("0");
bw.flush();
} else {
int x, y;
map = new int[h + 1][n + 1];
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
map[x][y] = 1;
map[x][y + 1] = 2;
}
for (int i = 0; i <= 3; i++) {
answer = i;
dfs(1, 0);
if (finish) break;
}
bw.write((finish) ? String.valueOf(answer) : "-1");
bw.flush();
}
}
private static void dfs(int x, int count) {
if (finish) return;
if (answer == count) {
if (check()) {
finish = true;
}
return;
}
for (int i = x; i < h + 1; i++) {
for (int j = 1; j < n; j++) {
if (map[i][j] == 0 && map[i][j + 1] == 0) {
map[i][j] = 1;
map[i][j + 1] = 2;
dfs(i, count + 1);
map[i][j] = map[i][j + 1] = 0;
}
}
}
}
private static boolean check() {
for (int i = 1; i <= n; i++) {
int x = 1, y = i;
for (int j = 0; j < h; j++) {
if (map[x][y] == 1){
y++;
} else if (map[x][y] == 2) {
y--;
}
x++;
}
if (y != i) {
return false;
}
}
return true;
}
}
풀이
2차원 int 배열을 선언하여 사다리를 표시한다. 1이면 오른쪽으로 가고 2면 왼쪽으로 가게 한다. 사다리를 타고 i번 세로선의 결과가 i번이 나와야 하므로, 이를 체크해주는 함수를 작성한다. 각 행에서 출발하여 아래로 내려가 만약 해당 위치가 1이면 오른쪽으로 한칸 이동하고, 2면 왼쪽으로 한칸 이동한다. 가로선의 개수를 1씩 늘리며 연산하여 조건에 맞는경우 finish를 true로 하여 그 다음 연산을 막는다. 0부터 시작해 1, 2, 3까지 순서대로 조건에 맞으면 바로 연산을 멈춰 해당 숫자를 출력한다.
'학습 내용 > 백준 문제풀이' 카테고리의 다른 글
백준 11559 자바 - Puyo Puyo (0) | 2023.03.28 |
---|---|
백준 17135 자바 - 캐슬 디펜스 (0) | 2023.03.28 |
백준 1135 자바 - 뉴스 전하기 (0) | 2023.03.28 |
백준 11000 자바 - 강의실 배정 (0) | 2023.03.27 |
백준 1790 자바 - 수 이어 쓰기 2 (0) | 2023.03.08 |