15684번: 사다리 조작 (acmicpc.net)
H x N 크기의 격자가 있는 것과 동일하다.
현재 세로 방향은 모든 점이 연결 돼 있는 것과 다름없다. 이제 가로를 연결해야 한다.
한 점을 선택하면 왼쪽 혹은 오른쪽의 한 점도 반드시 선택해야 한다.
그런데 다른 한 점이 이미 다른 점과 인접해 있다면 그 점은 선택이 불가능하다.
각 열에서 시작해 그래프를 탐색해 나갈 것이다. 이때 도착점의 열 번호가 시작점의 열 번호와 같게 하기 위해 가로선을 최소 몇 개 추가해야 하는가.
우선 대전제는 시작점에서 r이 증가해 가는 방향으로 이동하는 것이다. 그리고 r이 마지막 H에 도달하는 게 종료지점이다.
이때 현재 위치에서 좌우로 움직일 수 있다면 반드시 해당 열로 이동해야 한다.
좌우로 움직일 수 있는지의 여부는 가로선의 존재 여부이다.
기존에 존재하던 가로선 이외에 새롭게 가로선을 배치할 수 있는 곳들을 파악해야 한다.
그리고 탐색을 진행해 가는데 모든 점이 자신의 점으로 도착하면 성공 하나라도 실패하면 이제 새롭게 가로선을 배치해야 한다.
필요 기능들을 생각해 보자.
- 탐색하는 기능
- 현재 지점에서 좌우로 이동이 가능한지 확인하는 기능
- 가로선을 추가하는 기능
가로선을 1개 놓는 경우, 2개 놓는 경우, 3개 놓는 경우를 체크해야 한다.
이렇게 했는데도 경로를 못 찾으면 -1 반환
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static FastReader scan = new FastReader();
static int N, M, H;
static int WIDTH;
static int[][] width;
static List<int[]> widthCandidate;
static int additionalCount = -1;
static void input() {
N = scan.nextInt();
M = scan.nextInt();
H = scan.nextInt();
WIDTH = 2 * N - 1;
width = new int[H][WIDTH];
for (int i = 0; i < M; i++) {
int r = scan.nextInt() - 1;
int c = scan.nextInt();
width[r][c + c - 1] = 1;
}
for (int c = 0; c < WIDTH; c += 2) {
for (int r = 0; r < H; r++) {
width[r][c] = 1;
}
}
widthCandidate = new ArrayList<>();
for (int row = 0; row < H; row++) {
for (int col = 1; col < WIDTH; col += 2) {
if (width[row][col] == 0) {
widthCandidate.add(new int[]{row, col});
}
}
}
}
static void print() {
for (int[] row : width) {
System.out.println(Arrays.toString(row));
}
System.out.println();
}
static boolean addWidth(int count, int depth, int next, int[][] width) {
if (depth == count) {
// count개의 다리를 놨다.
if (allPathSuccess()) return true;
return false;
}
for (int i = next; i < widthCandidate.size(); i++) {
int[] cand = widthCandidate.get(i);
int r = cand[0];
int c = cand[1];
if (canAdd(r, c, width)) {
width[r][c] = 1;
if (addWidth(count, depth + 1, i + 1, width)) {
return true;
};
width[r][c] = 0;
}
}
return false;
}
static boolean canAdd(int r, int c, int[][] width) {
boolean left = true;
boolean right = true;
if (isValidPosition(r, c - 2)) {
left = width[r][c - 2] != 1;
}
if (isValidPosition(r, c + 2)) {
right = width[r][c + 2] != 1;
}
return left && right;
}
static boolean allPathSuccess() {
int cnt = 0;
for (int c = 0; c <= WIDTH; c += 2) {
if (play(c, 0, c, new boolean[H][WIDTH])) {
cnt++;
}
}
return cnt == N;
}
static boolean play(int startC, int r, int c, boolean[][] visited) {
if (r == H) {
if (startC == c) {
return true;
}
return false;
}
visited[r][c] = true;
if (canMoveRight(r, c) && !visited[r][c + 2]) {
return play(startC, r, c + 2, visited);
} else if (canMoveLeft(r, c) && !visited[r][c - 2]) {
return play(startC, r, c - 2, visited);
} else {
return play(startC, r + 1, c, visited);
}
}
static boolean isValidPosition(int r, int c) {
return r >= 0 && r < H && c >= 0 && c < WIDTH;
}
static boolean canMoveRight(int r, int c) {
return isValidPosition(r, c + 1) && width[r][c + 1] == 1;
}
static boolean canMoveLeft(int r, int c) {
return isValidPosition(r, c - 1) && width[r][c - 1] == 1;
}
public static void main(String[] args) {
input();
if (allPathSuccess()) {
additionalCount = 0;
} else {
for (int count = 1; count <= 3; count++) {
if (addWidth(count, 0, 0, width)) {
additionalCount = count;
break;
}
}
}
System.out.println(additionalCount);
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}
이렇게 풀었는데 시간초과가 발생했다.
이동해서 판정하는 로직에서 재귀를 사용함으로써 스택이 깊어져 시간 효율성이 떨어지는 문제를 해결하기 위해 반복문으로 변경했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static FastReader scan = new FastReader();
static int N, M, H;
static int WIDTH;
static int[][] width;
static List<int[]> widthCandidate;
static int additionalCount = -1;
static void input() {
N = scan.nextInt();
M = scan.nextInt();
H = scan.nextInt();
WIDTH = 2 * N - 1;
width = new int[H][WIDTH];
for (int i = 0; i < M; i++) {
int r = scan.nextInt() - 1;
int c = scan.nextInt();
width[r][c + c - 1] = 1;
}
for (int c = 0; c < WIDTH; c += 2) {
for (int r = 0; r < H; r++) {
width[r][c] = 1;
}
}
widthCandidate = new ArrayList<>();
for (int row = 0; row < H; row++) {
for (int col = 1; col < WIDTH; col += 2) {
if (width[row][col] == 0) {
widthCandidate.add(new int[]{row, col});
}
}
}
}
static void print() {
for (int[] row : width) {
System.out.println(Arrays.toString(row));
}
System.out.println();
}
static boolean addWidth(int count, int depth, int next, int[][] width) {
if (depth == count) {
// count개의 다리를 놨다.
if (allPathSuccess()) return true;
return false;
}
for (int i = next; i < widthCandidate.size(); i++) {
int[] cand = widthCandidate.get(i);
int r = cand[0];
int c = cand[1];
if (canAdd(r, c, width)) {
width[r][c] = 1;
if (addWidth(count, depth + 1, i + 1, width)) {
return true;
};
width[r][c] = 0;
}
}
return false;
}
static boolean canAdd(int r, int c, int[][] width) {
boolean left = true;
boolean right = true;
if (isValidPosition(r, c - 2)) {
left = width[r][c - 2] != 1;
}
if (isValidPosition(r, c + 2)) {
right = width[r][c + 2] != 1;
}
return left && right;
}
static boolean allPathSuccess() {
for (int i = 0; i < N; i++) {
int c = i * 2; // 세로선 위치
int currentC = c;
for (int r = 0; r < H; r++) {
// 오른쪽으로 이동
if (canMoveRight(r, currentC)) {
currentC += 2;
}
// 왼쪽으로 이동
else if (canMoveLeft(r, currentC)) {
currentC -= 2;
}
// 아래로 이동 (별도 처리 필요 없음)
}
if (currentC != c) {
return false;
}
}
return true;
}
static boolean isValidPosition(int r, int c) {
return r >= 0 && r < H && c >= 0 && c < WIDTH;
}
static boolean canMoveRight(int r, int c) {
return isValidPosition(r, c + 1) && width[r][c + 1] == 1;
}
static boolean canMoveLeft(int r, int c) {
return isValidPosition(r, c - 1) && width[r][c - 1] == 1;
}
public static void main(String[] args) {
input();
for (int i = 0; i <= 3; i++) {
if (addWidth(i, 0, 0, width)) {
System.out.println(i);
return;
}
}
System.out.println(-1);
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}
