삼성 sw 역량 테스트 - 사다리 조작(15684번)

1. 개요

 삼성 sw 역량 테스트 기출 문제인 사다리 조작을 아래와 같은 구조로 풀어보겠습니다. 혹시나 코드 이해가 되지 않는다면 간단한 셈플 문제를 확인해 주시기 바랍니다.

2. 문제 분석

 백준 홈페이지의 문제에서 명시된 조건들은 다음과 같습니다.

    ① 목표 : 최소 연결선을 그어 들어온 라인과 나가는 라인이 같도록 만듭니다.

    ② 세로선 : 2<=N<=10

    ③ 가로선 : 0<=M<=270

    ④ 연결선 : 1<=H<=30, 가로선 하나당 최소 연결선이 1개 이상 있어야 합니다.

    ⑤ 연속적으로 연결선을 긋지 못합니다.

    ⑥ 결과가 3보다 크거나 불가능 하면 -1 출력합니다.

3. 소스코드

 이번 문제는 다른 문제와 다르게 2번과 3번 순서가 바뀌어 있습니다. 솔직하게 왜 순서를 바꾸지 않으면 시간 초과가 나는지 잘모르겠습니다.

제 코드의 DFS 소스 코드를 먼저 보시겠습니다. 

전체 코드입니다.

#include <iostream> using namespace std; #define MIN(X,Y) ((X) < (Y) ? (X) : (Y)) int Raw, Colum; bool arr[31][11]; int result = 4; void print() { for (int i = 0; i < Raw; i++) { for (int j = 0; j < Colum; j++) { cout << arr[i][j]; } cout << endl; } cout << endl; } bool drawCheck(int raw, int colum) { if (colum == 0) { if (!arr[raw][1]) return true; } else if (colum == Colum - 1) { if (!arr[raw][colum - 1]) return true; } else { if (!arr[raw][colum - 1] && !arr[raw][colum + 1]) return true; } return false; } bool check() { int at; for (int content = 0; content <= Colum; content++) { at = content; for (int line = 0; line <= Raw; line++) { if (at == Colum) { if (arr[line][at - 1]) at--; } else if (at == 0) { if (arr[line][at]) at++; } else { if (arr[line][at - 1]) at--; else if (arr[line][at]) at++; } } if (at != content) return false; } return true; } void draw(int line, int content, int count) { if (count < result) { // 그은 최소 횟수가 현재 그은 횟수보다 작을 때 if (line == Raw) { if (check()) result = MIN(result, count); return; } if (!arr[line][content]) { // 색칠 안되어 있다면 if (drawCheck(line, content)) { // 색칠 가능하면 arr[line][content] = true; // 색칠 if (content + 2 >= Colum) draw(line + 1, 0, count + 1); else draw(line, content + 2, count + 1); arr[line][content] = false; // 색칠 지우기 } if (content + 1 == Colum) draw(line + 1, 0, count); else draw(line, content + 1, count); } else { // 색칠이 되어 있다면... if (content + 2 >= Colum) draw(line + 1, 0, count); else draw(line, content + 2, count); } } } int main() { int T; cin >> Colum >> T >> Raw; Colum--; for (int i = 0; i < Raw; i++) { for (int j = 0; j < Colum; j++) { arr[i][j] = false; } } int line, content; for (int i = 0; i < T; i++) { cin >> line >> content; arr[line - 1][content - 1] = true; } draw(0, 0, 0); if (result == 4) result = -1; cout << result; }