[ 백준 15684 사다리조작 ] 문제 풀이(Java) - 삼성 SW역량테스트 기출

 

오늘은 삼성 SW역량테스트 기출 '사다리 조작' 문제를 풀어보았습니다.

 

백트래킹과 시뮬레이션 관련 문제로 시간 초과에 주의해야하는 문제입니다!!

(완전탐색했다가 시간초과로 고생했다,,,)

 

 

문제보기

https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

 

나의 풀이

 

백트래킹을 하기에 앞서 사다리를 어떤 자료구조로 정의해줄지를 정해주어야 합니다.

사다리는 가로선과 세로선으로 이루어져 있으므로 배열을 이용해서 구현해주도록 하겠습니다!

 

<배열 정의>

A[i][j] : j번째 세로선과 j+1번째 세로선을 연결하는 i번째 가로선이 연결되어 있는지 여부

 

해당 배열 값이 0이면 연결되어 있지 않은 상태, 1이면 연결되어 있는 상태로 정의했습니다.

 

그리고 주의할 점!

가로선과 세로선 모두 1부터 시작하므로 배열 크기 지정할 때 [가로선 개수+1][세로선 개수+1]로 정의해주어야 합니다!!

 

사다리를 정의한 후 가로선을 설치할 3개를 구해주면 됩니다.

 

[처음 풀이]

 

처음 구현했던 방식은 배열의 모든 칸에 대해서 이미 연결되어 있는 칸은 index+2로 넘어가고, 연결되어 있지 않은 칸은 재귀에 의해 연결 여부를 선택해서 모든 칸에 대해서 조사했을 때 연결하고자 하는 가로선의 개수가 3개 이하인 경우에 대해서만 사다리 조건(i번째 세로선은 i로 도착해야한다)을 만족하는지 여부를 조사했는데 시간 초과가 났습니다,,,

 

//브루트 포스 + 시뮬레이션 문제
//시간초과 버전

import java.io.*;
import java.util.*;

public class N_15684 {
	static class Point {
		int i;
		int j;

		Point(int i, int j) {
			this.i = i;
			this.j = j;
		}
	}

	static int[][] A;
	static ArrayList<Point> list = new ArrayList<Point>();
	static int min = Integer.MAX_VALUE;

	static void go(int index, int selected) {
		if (selected >= 4)
			return;
		if (index >= A.length * A[0].length) {
			if (selected <= 3) {
				int[][] B = new int[A.length][A[0].length];
				for (int i = 0; i < B.length; i++)
					B[i] = A[i].clone();

				// list에 있는 가로선 B에 추가
				for (int i = 0; i < list.size(); i++) {
					B[list.get(i).i][list.get(i).j] = 1;
				}

				// 사다리 타기 시뮬레이션
				for (int i = 1; i < B[0].length; i++) {
					int curVertical = i;
					int curHorizontal = 0;

					while (curHorizontal != B.length - 1) {
						curHorizontal++;
						if (B[curHorizontal][curVertical - 1] == 1) {
							curVertical--;
						} else if (B[curHorizontal][curVertical] == 1) {
							curVertical++;
						}

					}
					if (curVertical != i)
						return;
				}

				// 최소값 비교
				if (min > list.size())
					min = list.size();
			}
			return;
		}
		int i = index / A[0].length;
		int j = index % A[0].length;

		if (i < 1 || j < 1 || j == A[0].length - 1) {
			if (i < 1)
				go(index + A[0].length, selected);
			else
				go(index + 1, selected);
		} else {
			if (A[i][j] == 0) {
				list.add(new Point(i, j));
				go(index + 2, selected + 1);
				list.remove(list.size() - 1);

				go(index + 1, selected);
			} else if (A[i][j] == 1) {
				go(index + 2, selected);
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String[] input = br.readLine().split(" ");
			int N = Integer.parseInt(input[0]); // 세로선 수
			int M = Integer.parseInt(input[1]); // 가로선 수
			int H = Integer.parseInt(input[2]); // 놓을 수 있는 가로줄 개수

			A = new int[H + 1][N + 1]; // 0이면 아직 연결 안 된 곳, 1이면 연결되어 있는 곳
			for (int i = 0; i < M; i++) {
				String[] arr = br.readLine().split(" ");
				A[Integer.parseInt(arr[0])][Integer.parseInt(arr[1])] = 1;
			}

			go(0, 0);
			if (min == Integer.MAX_VALUE)
				System.out.println(-1);
			else
				System.out.println(min);
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

 

그래서 해당 문제는 백트래킹을 해주어야 합니다!

 

가로선은 최대 3개까지 그을 수 있고 그 중에서 최소값을 찾아야 하므로 저는 재귀 함수를 약간 수정해서 가로선을 0개 연결하는 경우, 1개 연결하는 경우, 2개 연결하는 경우, 3개 연결하는 경우로 나눠서 앞선 개수에서 이미 방법이 존재한다면 이후 개수는 구하지 않는 방식으로 고쳐주었더니 시간초과가 해결되었습니다!!

 

go(index, selected)     : 현재 배열 칸 index, 선택한 가로선 개수

 

에서

 

go(index, selected, goal)     : 현재 배열 칸 index, 선택한 가로선 개수, 목표 가로선 개수

 

goal 변수를 추가해 지금 설치하고자 하는 가로선의 개수를 지정해주었습니다.

 

 

코드

 

//브루트 포스 + 시뮬레이션 문제

import java.io.*;
import java.util.*;

public class N_15684_v2 {
	static class Point {
		int i;
		int j;

		Point(int i, int j) {
			this.i = i;
			this.j = j;
		}
	}

	static int[][] A;
	static ArrayList<Point> list = new ArrayList<Point>();
	static int min = Integer.MAX_VALUE;

	static void go(int index, int selected, int goal) {
		if (selected == goal) {
			int[][] B = new int[A.length][A[0].length];
			for (int i = 0; i < B.length; i++)
				B[i] = A[i].clone();

			// list에 있는 가로선 B에 추가
			for (int i = 0; i < list.size(); i++) {
				B[list.get(i).i][list.get(i).j] = 1;
			}

			// 사다리 타기 시뮬레이션
			for (int i = 1; i < B[0].length; i++) {
				int curVertical = i;
				int curHorizontal = 0;

				while (curHorizontal != B.length - 1) {
					curHorizontal++;
					if (B[curHorizontal][curVertical - 1] == 1) {
						curVertical--;
					} else if (B[curHorizontal][curVertical] == 1) {
						curVertical++;
					}
				}
				if (curVertical != i)
					return;

			}
			// 최소값 비교
			if (min > list.size())
				min = list.size();
			return;
		}

		if (index >= A.length * A[0].length)
			return;

		int i = index / A[0].length;
		int j = index % A[0].length;

		if (i < 1 || j < 1 || j == A[0].length - 1) {
			if (i < 1)
				go(index + A[0].length, selected, goal);
			else
				go(index + 1, selected, goal);
		} else {
			if (A[i][j] == 0) {
				list.add(new Point(i, j));
				go(index + 2, selected + 1, goal);
				list.remove(list.size() - 1);

				go(index + 1, selected, goal);
			} else if (A[i][j] == 1) {
				go(index + 2, selected, goal);
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String[] input = br.readLine().split(" ");
			int N = Integer.parseInt(input[0]); // 세로선 수
			int M = Integer.parseInt(input[1]); // 가로선 수
			int H = Integer.parseInt(input[2]); // 놓을 수 있는 가로줄 개수

			A = new int[H + 1][N + 1]; // 0이면 아직 연결 안 된 곳, 1이면 연결되어 있는 곳
			for (int i = 0; i < M; i++) {
				String[] arr = br.readLine().split(" ");
				A[Integer.parseInt(arr[0])][Integer.parseInt(arr[1])] = 1;
			}

			// 사다리 0개 추가
			go(0, 0, 0);
			if (min == 0) {
				System.out.println(min);
				System.exit(0);
			}

			// 사다리 1개 추가
			go(0, 0, 1);
			if (min == 1) {
				System.out.println(min);
				System.exit(0);
			}

			// 사다리 2개 추가
			go(0, 0, 2);
			if (min == 2) {
				System.out.println(min);
				System.exit(0);
			}

			// 사다리 3개 추가
			go(0, 0, 3);
			if (min == 3) {
				System.out.println(min);
				System.exit(0);
			}

			System.out.println(-1);
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

 

 

결과

 

시간초과와의 사투,,,,