kahuz

/////////////////////////////////////////////////////////////////////////////
// Name:        minimal.cpp
// Purpose:     Minimal wxWidgets sample
// Author:      Julian Smart
// Modified by:
// Created:     04/01/98
// Copyright:   (c) Julian Smart
// Licence:     wxWindows licence
/////////////////////////////////////////////////////////////////////////////

kahuz

//단순 시뮬레이션이라서 주석을 따로 남기지 않는다
//그저 주어진 조건을 그대로 코딩하면 되는 문제
#include <iostream>
#include <string>

using namespace std;

#define KING 1
#define STONE 2
int map[8][8] = { 0 };

kahuz

// 17141 연구소2
// 조건 - NxN크기의 연구소는 빈칸(0,2), 벽(1)으로 이루어져있고
// 빈칸의 일부는 바이러스를 놓을 수 있는 칸(2) ( 바이러스 칸은 빈칸으로도 취급된다 )
// 바이러스는 1초에 상, 하, 좌, 우 인접한 칸으로 "동시에" 복제 된다
// 이때 모든 빈칸(0,2)에 바이러스를 퍼트리는 최소 시간을 구해보자
// 로직
// 1. 임의의 위치에 바이러스 M개를 놓는다
// 2. 신호와 동시에 바이러스를 퍼트린다
// 3. 모든 빈칸이 바이러스로 전염되는 최소 시간을 구하자
// 입력

kahuz

//BFS와 BackTracking을 이용해 풀 수 있는 문제
//문제의 요지는 다음과 같다
//1. 입력으로 주어지는 바둑판은 고정된다.
//2. 고정된 바둑판에 2개의 수를 놓을 수 있다.
//3. 내가 임의로 2개의 수를 놓게 되었을 때, 상대방을 가장 많이 잡을 수 있는 경우를 찾아라
//4. 상대방을 잡는 조건은 상대방이 나에게 둘러쌓여 더이상 연결된 바둑돌을 놓을 수 없는 상태이다.

#include <iostream>	//io
#include <queue>	//queue
#include <cstring>	//memset

kahuz

//백트래킹 형태로 접근하는 문제 ( 사실 DFS로 푸는 많은 문제들이 결과적으로 백트래킹 형태를 띈다고 생각한다 )
// 1. 현재 접근 요소가 이전에 접근한 요소에 해당되는가
// 2. 배열 범위를 넘어서는가
#include <iostream>
#include <string>

using namespace std;

//이미 접근한 알파벳인지 확인하기 위한 배열 선언 및 초기화
bool exist_alphbet[26] = { 0 };

kahuz

//제대로 접근한 코드
//가진 종이를 사용할 수 있는 모든 경우의 수를 다 확인하여
//최종적으로 가장 적은 결과값이 나오는 경우를 리턴하였다
//문제 풀이를 위한 로직을 생각하기는 어렵지 않으나
//많은 조건들로 인해 구현이 어려웠던 문제
#include <iostream>		//io

using namespace std;
//종이를 표시할 지도 배열 선언 및 초기화
int map[10][10] = { 0 };

kahuz

// 구현 방법에 대해 어렵게 접근했던 문제
// 정말 간단하게 모든 탐색 경우를 생각하여
// 6자리 숫자를 만든 것들에 대해 나열하면 되는 문제이다
// 알고리즘 유형이 백트레킹이라하여 기존 DFS/BFS 문제 풀이와 다르게 접근할 필요가 없다.
#include <iostream>	// io

using namespace std;
//숫자판 가로 세로 생성
int N = 5;
//입력받을 숫자판의 배열 선언 및 초기화

kahuz

// 구현 방법에 대해 어렵게 접근했던 문제
// 정말 간단하게 모든 탐색 경우를 생각하여
// 6자리 숫자를 만든 것들에 대해 나열하면 되는 문제이다
// 알고리즘 유형이 백트레킹이라하여 기존 DFS/BFS 문제 풀이와 다르게 접근할 필요가 없다.
#include <iostream>	// io

using namespace std;
//숫자판 가로 세로 생성
int N = 5;
//입력받을 숫자판의 배열 선언 및 초기화

kahuz

//백트래킹의 대표적인 문제
//퀸의 위치를 정하기 위한 제한 조건을 어떻게 주냐에 따라 구현 난이도가 달라진다
#include <iostream>     //  io

using namespace std;
//체스판의 크기이자 퀸의 개수 변수 선언 및 초기화
int N = 0;
//결과값을 저장할 변수 선언 및 초기화
int res = 0;
//행을 기준으로 본 ( 열로 생각해도 상관이 없다 ) , 배열 선언 및 초기화

kahuz

#include <iostream>		//io
#include <cstring>		//memset
using namespace std;

//테스트 케이스와 노드의 수를 저장할 변수 선언 및 초기화
int T = 0, N = 0;
//결과값을 저장할 변수 선언, 초기화는 테스트 루프에서 진행
int res;
//인전행렬 선언 및 초기화
int arr[100001] = { 0 };