삼성 sw 역량 테스트 - DFS 셈플 예제

1. 개요

 삼성 sw 역량 테스트 문제 중 DFS를 활용하여 풀 수 있는 문제들을 풀기 위한 기초 바탕 코드입니다. 항상 배열을 활용하였으며 아래와 같이 3개의 구조를 가지고 있습니다. 

      

2. 예제

셈플 문제 :  3x3 배열에서 3곳을 색칠할 수 있는 모든 경우를 출력하시오.

#include <iostream> using namespace std; int Raw, Colum; bool arr[3][3]; int result = 0; void print_arr() { for (int i = 0; i < Raw; i++) { for (int j = 0; j < Colum; j++) { cout << arr[i][j]; } cout << endl; } cout << endl; } void check(int c_raw, int c_colum, int count) { if (count == 3) { //목표 조건 충족 print_arr(); result++; }else{ if (c_raw == Raw) { //범위 벗어남 return; } else { arr[c_raw][c_colum] = true; //색칠 if (c_colum + 1 == Colum) check(c_raw + 1, 0, count + 1); else check(c_raw, c_colum + 1, count + 1); arr[c_raw][c_colum] = false; //색칠 지움 if (c_colum + 1 == Colum) check(c_raw + 1, 0, count); else check(c_raw, c_colum + 1, count); } } } int main() { //cin >> Raw >> Colum; Raw = 3; Colum = 3; for (int i = 0; i<Raw; i++) { for (int j = 0; j<Colum; j++) { //cin >> arr[i][j]; arr[i][j] = false; } } check(0,0,0); }