백준 15684 사다리 조작 - 삼성 SW 역량 테스트 기출

백준 15684 사다리 조작 - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

15684번: 사다리 조작

 

2. 문제 해결에 대한 아이디어

1. 이 문제 구현에서 까다롭게 생각된 건 아래 내용이다.

   . 왼쪽으로 움직일지 오른쪽으로 움직일지 판단하는 방법

   . 가로선은 연속하지 않으므로 횡 이동하면 다음 이동은 무조건 아래이다.

2. 위 내용에 대한 아이디어를 떠올리면 쉬운 문제였다.

3. 왼쪽으로 움직일지 오른쪽으로 움직일지는 격자에 숫자로 표시했다.

   . 1 = 오른쪽으로 움직임 / 2 = 왼쪽으로 움직임

   . board[i][j] = 1 / board[i][j + 1] = 2

4. 추가 가로선을 3개보다 많이 그려야하는 경우는 -1을 출력하므로 최대 3개까지 그리는 경우만 생각한다.

5. 가로선의 위치를 정할 때, 재귀에서 다음 재귀로 넘어갈 떄 중복탐색을 막기 위해 아래처럼 구현했다.

   . j + 1 == N - 1인 경우 (가로선을 그을 때 기준점이 가질 수 있는 최대 열은 N-1이다.

      . select(i + 1, 0, depth + 1, end); (다음 행의 0번째 열부터 탐색하도록)

   . 그렇지 않은 경우

      . select(i, j + 1, depth + 1, end);

   . 이렇게 하면 이전 재귀에서 탐색한 위치의 다음 위치부터 탐색해나간다.

   . j 에 대한 for 문이 끝나면 indexJ를 0으로 초기화 시켜야한다.

      . 초기화 시키지 않으면 다음 행으로 넘어가서도 indexJ 열부터 탐색하게 된다.

6. 가로선 그리기가 완료되면 각 번호에서 사다리를 타고 내려와서 동일한 번호로 이동하는지 확인한다.

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static class Pair {
		int y, x;

		public Pair(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}

		public Pair(Pair p) {
			super();
			this.y = p.y;
			this.x = p.x;
		}

	}

	static int N, M, H;
	static int[][] board;
	static int answer = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] nmh = br.readLine().split(" ");

		N = Integer.parseInt(nmh[0]);
		M = Integer.parseInt(nmh[1]);
		H = Integer.parseInt(nmh[2]);

		board = new int[H][N];

		for (int i = 0; i < M; i++) {
			String[] yx = br.readLine().split(" ");
			// 위치 보정
			int y = Integer.parseInt(yx[0]) - 1;
			int x = Integer.parseInt(yx[1]) - 1;
			board[y][x] = 1;
			board[y][x + 1] = 2;
		}

		for (int end = 0; end < 4; end++) {
			select(0, 0, 0, end);
		}

		if (answer == Integer.MAX_VALUE)
			answer = -1;

		System.out.println(answer);

	}

	static void select(int indexI, int indexJ, int depth, int end) {
		if (depth == end) {
			if (move()) {
				answer = Math.min(answer, end);
			}
			return;
		}

		for (int i = indexI; i < H; i++) {
			for (int j = indexJ; j < N - 1; j++) {
				if (board[i][j] != 0 || board[i][j + 1] != 0)
					continue;
				board[i][j] = 1;
				board[i][j + 1] = 2;
				if (j + 1 == N - 1) {
					select(i + 1, 0, depth + 1, end);
				} else {
					select(i, j + 1, depth + 1, end);
				}

				board[i][j] = 0;
				board[i][j + 1] = 0;
			}
			indexJ = 0;
		}
	}

	static boolean move() {

		for (int j = 0; j < N; j++) {

			int y = 0;
			int x = j;

			while (y < H) {
				// 1이면 오른쪽
				if (board[y][x] == 1) {
					++x;
				}
				// 2면 왼쪽
				else if (board[y][x] == 2) {
					--x;
				}
				++y;
			}

			if (x != j)
				return false;
		}

		return true;
	}

}

 

4. 채점 결과

 

5. 느낀 점

1. 왼쪽, 오른쪽 이동의 판단 그리고 가로선은 연속하지 않기에 무조건 아래로 이동하는 것을 떠올리기 힘들었다.

2. 재귀를 통한 2차원 배열의 완전 탐색에서 위치를 중복하지 않고 탐색하는 방법을 깨달았다.