SW 역량테스트 - [백준] 사다리 조작 문제 풀이/해답/코드 (C++ / JAVA)

---

SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 

---

문제 링크 : www.acmicpc.net/problem/15684

해답 코드 : 

 

#include<cstdio>
int N, M, H, minCnt = 9999999, map[31][11];

// 자기 자신과 매칭되는 사다리인지 판단하는 함수
bool checkLadder() {
	for (int i = 1, pos; i <= N; i++) {
		pos = i;
		for (int j = 1; j <= H; j++) {
			if (map[j][pos] == 1)    pos++;
			else if (map[j][pos - 1] == 1) pos--;
		}
		if (i != pos) return false;
	}
	return true;
}


// 재귀함수 : (x, y) 부터 사다리를 추가하여 사다리 개수의 최소값을 구함, cnt는 현재 추가된 사다리 개수
void func(int cnt, int x, int y) {

	// 불필요한 탐색을 탈출하는 조건 (가지치기, 백트래킹)
	if (cnt >= minCnt) return;

	// 종료 부
	if (checkLadder()) {
		minCnt = cnt;
		return;
	}
	if (cnt == 3) return;


	for (int i = y; i <= H; i++, x = 1)
		for (int j = x; j < N; j++) {
			if (map[i][j] || map[i][j+1] || map[i][j - 1]) {
				continue;
			}

			map[i][j] = 1; // 사다리 추가, 해결 부
			func(cnt + 1, j + 2, i); //분할 부
			map[i][j] = 0;
		}
}
int main() {
	scanf("%d%d%d", &N, &M, &H);
	for (int i = 0, a, b; i < M; i++) {
		scanf("%d%d", &a, &b);
		map[a][b] = 1;
	}
	func(0, 1, 1);
	if (minCnt>3) printf("-1");
	else printf("%d", minCnt);
	return 0;
}

 

 

// java

import java.util.Scanner;

public class ladder {

    static int N, M, H;
    static int minCnt = 999999;
    static int[][] ladder = new int[31][11];

    static boolean checkLadder(int[][] ladder) {
        for (int i = 1, pos; i <= N; i++) {
            pos = i;
            for (int j = 1; j <= H; j++) {
                if(ladder[j][pos] == 1) pos++;
                else if (ladder[j][pos-1] == 1) pos--;
            }
            if (i != pos) return false;
        }
        return true;
    }

    static void backtrack(int[][] ladder, int cnt, int x, int y) {

        // 탈출조건
        if (cnt >= minCnt) return;

        // Terminator
        if (checkLadder(ladder)) {
            minCnt = cnt;
            return;
        }

        if (cnt == 3) return;

        for (int i = y; i <=H; i++, x = 1) {
            for (int j = x; j < N; j++) {
                if (ladder[i][j] == 1 || ladder[i][j+1] == 1 || ladder[i][j-1] == 1) {
                    continue;
                }
                ladder[i][j] = 1;
                backtrack(ladder, cnt + 1, j+2, i);
                ladder[i][j] = 0;
            }
        }
    }

    public static void main(String args[]) {

        int output;

        Scanner sc = new Scanner(System.in);


        N = sc.nextInt();
        M = sc.nextInt();
        H = sc.nextInt();

        for (int i = 0; i < M; i++) {
            ladder[sc.nextInt()][sc.nextInt()] = 1;
        }

        backtrack(ladder, 0, 1, 1);

        if (minCnt > 3) System.out.println("-1");

        else System.out.println(minCnt);

    }
}

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제