JAVA/알고리즘 서브 노트
[백준 15684 : JAVA] 사다리 조작
Kamea
2022. 10. 30. 12:29
https://www.acmicpc.net/problem/15684
15684번: 사다리 조작
사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선
www.acmicpc.net
[1회차] 10월 29일 ~ 10월 30일 : 거드름의 결과랄까...^^
문제 접근 방법 (사용 자료구조, 알고리즘)
이 문제는 시행착오가 많았어서 차례로 한번 보여줄까 한다
(1) 자료구조 (List + HashMap) + 조합
입력
(1) {N, M, H}
(2) 연결할 수 있는 사다리의 후보군들을 저장해 놓는 candidates(Point 리스트)에 (N) * (H + 1)개의 사다리를 넣어 놓는다
(3) {M개의 줄에는 연결되어 있는 사다리의 정보}를 입력 받으며 후보군에서 (사다리 + 해당 사다리와 연속된 위치에 있는 사다리) 를 빼준다 (remove) + info(HashMap<String, Integer>)에 key값으로는 위치, value는 1 또는 -1을 넣어준다.
→ 현재 사다리 정보가 (a, b)라면 (a, b) - (a,b+1) 이렇게 연결하므로 a+","+b 에는 1을, a+","+(b+1)에는 -1을 넣어준다
→ 사다리 이동 위치
로직
(1) M = 0 인 경우에는 진행하지 않고 0을 출력한다.
(2) candidates 에서 차례로 0, 1, 2, 3개의 사다리를 뽑는 경우의 수를 조합한다. → DFS
(3) 수를 다 조합했을 경우, 사다리를 탄다
(4) Point 객체에 (현재 탈 줄의 숫자(x), 현재 높이(y, 1)) 를 넣어주고 높이가 H까지 갈때 까지 이동을 한다.
(5) info에 해당 위치의 값이 있다면 해당 value 만큼 더해준다 → 1이면 현재 위치 기준으로 오른쪽, -1 이면 왼쪽으로 이동
(6) 만약 현재 탈 줄의 숫자와 맨 마지막 도착 위치가 맞지 않다면 더 이상 이동하지 않는다.
(7) 사다리를 타는 메서드에서 true를 반환할 경우 모든 재귀와 반복문을 종료하고 정답을 출력한다.
출력
3이상 또는 -1의 값에는 -1, 그 이외에는 찾은 정답을 출력한다.
결과 : 시간초과
대충 예상은 했는데 로직만 짜여진 느낌..?
코드
더보기
import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
public class Main {
static int N, M, H, selected[], ans;
static List<Point> candidates;
static Map<String, Integer> info;
static boolean visited[];
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
// 1. 입력
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
if(M == 0) {
System.out.println(0);
System.exit(0);
}
candidates = new ArrayList<>();
for (int i = 1; i < N; i++) {
for (int j = 1; j <= H; j++) {
candidates.add(new Point(j, i));
}
}
info = new HashMap<>();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(in.readLine());
// (a, b) - (a, b+1)를 이어줌
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
// 사다리 있다고 체크 해주기
info.put(a+","+b, 1);
info.put(a+","+(b+1), -1);
// 본인 + 연속하는 사다리를 계산해서 후보군에서 빼주기
candidates.remove(new Point(a, b));
if(b - 1 >= 1) candidates.remove(new Point(a, b-1));
if(b + 1 <= N) candidates.remove(new Point(a, b+1));
}
// 2-1. 사다리 설치할 곳 뽑기 1 또는 2
for (int i = 1; i <= 3 && ans == 0; i++) {
selected = new int[i];
visited = new boolean[candidates.size()];
combi(i, 0, 0);
}
System.out.println(ans == 0? -1: ans);
}
private static void combi(int D, int depth, int start) {
if(depth == D) {
// 사다리 추가하기
for (int i = 0; i < D; i++) {
Point ladder = candidates.get(selected[i]);
info.put(ladder.x+","+ladder.y, 1);
info.put(ladder.x+","+(ladder.y+1), -1);
}
// 사다리 타기
if(game()) {
ans = D;
return;
}
for (int i = 0; i < D; i++) {
Point ladder = candidates.get(selected[i]);
info.put(ladder.x+","+ladder.y, 0);
info.put(ladder.x+","+(ladder.y+1), 0);
}
return;
}
for (int i = start, size = candidates.size(); i < size && ans == 0; i++) {
if(!visited[i]) {
visited[i] = true;
selected[depth] = i;
combi(D, depth+1, i+1);
visited[i] = false;
}
}
}
private static boolean game() {
for (int i = 1; i <= N; i++) {
Point pos = new Point(i, 1);
while(pos.y <= H) {
// 사다리랑 만나는지 확인 -> 만난다면 pos[0] 이동시켜주기
if(info.get(pos.y+","+pos.x) != null && info.get(pos.y+","+pos.x) != 0) {
pos.x += Integer.valueOf(info.get(pos.y+","+pos.x));
}
pos.y += 1;
}
if(pos.x != i) return false;
}
return true;
}
}
(2) 자료구조 (List + boolean[][]) + 조합
입력
(1) {N, M, H}
(2) 연결할 수 있는 사다리의 후보군들을 저장해 놓는 candidates(Point 리스트)에 (N) * (H + 1)개의 사다리를 넣어 놓는다
(3) {M개의 줄에는 연결되어 있는 사다리의 정보}를 입력 받으며 후보군에서 (사다리 + 해당 사다리와 연속된 위치에 있는 사다리) 를 빼준다 (remove) + ladderCheck(boolean[H+1][N+1])를 true 로 설정해준다.
로직
(1) M = 0 인 경우에는 진행하지 않고 0을 출력한다.
(2) candidates 에서 차례로 0, 1, 2, 3개의 사다리를 뽑는 경우의 수를 조합한다. → DFS
(3) 수를 다 조합했을 경우, ladderCheck를 복사한 배열(copy)에 연결할 사다리 정보를 true로 설정한 후 사다리를 탄다.
(4) Point 객체에 (현재 탈 줄의 숫자(x), 현재 높이(y, 1)) 를 넣어주고 높이가 H까지 갈때 까지 이동을 한다.
(5) copy[y][x] = true면 x에 1을 더해주고 그렇지 않다면 copy[y][x-1] = true이면 1을 빼준다.
(6) 만약 현재 탈 줄의 숫자와 맨 마지막 도착 위치가 맞지 않다면 더 이상 이동하지 않는다.
(7) 사다리를 타는 메서드에서 true를 반환할 경우 모든 재귀와 반복문을 종료하고 정답을 출력한다.
출력
3이상 또는 -1의 값에는 -1, 그 이외에는 찾은 정답을 출력한다.
메모리 & 시간
어마무시한 메모리와 시간, 심지어 컴파일러에 따라 시간 차이가 많이 나는데 이유는 모르겠다.
뭔가 수정할 필요를 느끼고 다시 한번의 수정에 돌입했다.
코드
더보기
import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
public class Main {
static int N, M, H, selected[], ans;
static List<Point> candidates;
static boolean visited[], ladderCheck[][], copy[][];
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
// 1. 입력
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
if(M == 0) {
System.out.println(0);
System.exit(0);
}
candidates = new ArrayList<>();
for (int i = 1; i < N; i++) {
for (int j = 1; j <= H; j++) {
candidates.add(new Point(j, i));
}
}
ladderCheck = new boolean[H + 1][N + 1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(in.readLine());
// (a, b) - (a, b+1)를 이어줌
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
// 사다리 있다고 체크 해주기
ladderCheck[a][b] = true;
// 본인 + 연속하는 사다리를 계산해서 후보군에서 빼주기
candidates.remove(new Point(a, b));
if(b - 1 >= 1) candidates.remove(new Point(a, b-1));
if(b + 1 <= N) candidates.remove(new Point(a, b+1));
}
ans = 4;
// 2-1. 사다리 설치할 곳 뽑기 1 또는 2
for (int i = 0; i <= 3 && ans == 4; i++) {
selected = new int[i];
visited = new boolean[candidates.size()];
combi(i, 0, 0);
}
System.out.println(ans == 4? -1: ans);
}
private static void combi(int D, int depth, int start) {
if(depth == D) {
copy = new boolean[H + 1][N + 1];
for (int i = 0; i <= H; i++) {
copy[i] = ladderCheck[i].clone();
}
// 사다리 추가하기
for (int i = 0; i < D; i++) {
Point ladder = candidates.get(selected[i]);
copy[ladder.x][ladder.y] = true;
}
// 사다리 타기
if(game()) {
ans = D;
return;
}
return;
}
for (int i = start, size = candidates.size(); i < size && ans == 4; i++) {
if(!visited[i]) {
visited[i] = true;
selected[depth] = i;
combi(D, depth+1, i+1);
visited[i] = false;
}
}
}
private static boolean game() {
for (int i = 1; i <= N; i++) {
Point pos = new Point(i, 1);
while(pos.y <= H) {
if(copy[pos.y][pos.x]) {
pos.x += 1;
} else if(pos.x - 1 >= 1 && copy[pos.y][pos.x-1]) {
pos.x -= 1;
}
pos.y += 1;
}
if(pos.x != i) return false;
}
return true;
}
}
(3) 자료구조 (List + boolean[][]) + 순열
입력
(1) {N, M, H}
(2) 연결할 수 있는 사다리의 후보군들을 저장해 놓는 candidates(Point 리스트)에 (N) * (H + 1)개의 사다리를 넣어 놓는다
(3) {M개의 줄에는 연결되어 있는 사다리의 정보}를 입력 받으며 후보군에서 (사다리 + 해당 사다리와 연속된 위치에 있는 사다리) 를 빼준다 (remove) + ladderCheck(boolean[H+1][N+1])를 true 로 설정해준다.
로직
(1) M = 0 인 경우와 사다리를 설치하지 않고도 이미 조작된 경우에는 진행하지 않고 0을 출력한다.
(2) candidates 에서 차례로 1, 2, 3개의 사다리를 뽑는 경우의 수를 순열로 생성한다.
→ 이 때 하나의 사다리를 연결할 때마다 사다리 타기를 해서 만약 사다리를 제대로 조작하지 못했으면 다음 재귀로 넘기고,
사다리를 제대로 조작했을 경우에는 재귀를 즉시 종료하고 답을 출력한다.
(4) Point 객체에 (현재 탈 줄의 숫자(x), 현재 높이(y, 1)) 를 넣어주고 높이가 H까지 갈때 까지 이동을 한다.
(5) copy[y][x] = true면 x에 1을 더해주고 그렇지 않다면 copy[y][x-1] = true이면 1을 빼준다.
(6) 만약 현재 탈 줄의 숫자와 맨 마지막 도착 위치가 맞지 않다면 false를 반환한다.
출력
3이상 또는 -1의 값에는 -1, 그 이외에는 찾은 정답을 출력한다.
메모리 & 시간
그 결과 아주 쬐끔 줄임
84ms 의 코드를 보았는데요 아예 후보군을 만들지 않고 하시더라구여...무슨 홀수 이렇게 해서.. 저는 아직 그 정도까지는 아닌 걸루...
코드
더보기
import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
public class Main {
static int N, M, H, ans;
static List<Point> candidates;
static boolean visited[], ladderCheck[][];
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
// 1. 입력
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
candidates = new ArrayList<>();
for (int i = 1; i < N; i++) {
for (int j = 1; j <= H; j++) {
candidates.add(new Point(j, i));
}
}
ladderCheck = new boolean[H + 1][N + 1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(in.readLine());
// (a, b) - (a, b+1)를 이어줌
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
// 사다리 있다고 체크 해주기
ladderCheck[a][b] = true;
// 본인 + 연속하는 사다리를 계산해서 후보군에서 빼주기
candidates.remove(new Point(a, b));
if(b - 1 >= 1) candidates.remove(new Point(a, b-1));
if(b + 1 <= N) candidates.remove(new Point(a, b+1));
}
if(M == 0|| game(ladderCheck)) {
System.out.println(0);
System.exit(0);
}
ans = 4;
for (int i = 1; i <= 3 && ans == 4; i++) {
visited = new boolean[candidates.size()];
combi(i, 0, ladderCheck);
}
System.out.println(ans == 4? -1: ans);
}
private static void combi(int D, int depth, boolean[][] laddercopy) {
if(depth == D) {
return;
}
for (int i = 0, size = candidates.size(); i < size && ans == 4; i++) {
if(!visited[i]) {
visited[i] = true;
laddercopy[candidates.get(i).x][candidates.get(i).y] = true;
if(!game(laddercopy)) {
combi(D, depth+1, laddercopy);
visited[i] = false;
laddercopy[candidates.get(i).x][candidates.get(i).y] = false;
} else {
ans = D;
break;
}
}
}
}
private static boolean game(boolean[][] copy) {
for (int i = 1; i <= N; i++) {
Point pos = new Point(i, 1);
while(pos.y <= H) {
if(copy[pos.y][pos.x]) {
pos.x += 1;
} else if(pos.x - 1 >= 1 && copy[pos.y][pos.x-1]) {
pos.x -= 1;
}
pos.y += 1;
}
if(pos.x != i) return false;
}
return true;
}
}
문제를 푼 시간 (문제 해석 + 문제 접근 + 코드 구현)
| 문제 해석 | 문제 접근 | 코드 구현 |
| 15분 | 20분 | 하루가 넘어감...잠 잔 시간까지 포함하면(13시간), 아니면 (2시간 30분) |