프밍노트

으른 상어

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

문제의 구조는

입력받기

상어의 이동 방향  데이터 받아오기

상어의 이동

상어의 냄새 남기기

순서로 진행한다.

위이미지처럼 1번 상어부터 

오른쪽을 보기에  맨 아래  오른쪽 왼쪽 위아래 순으로 탐색한다.

냄새를 남긴다.

만약 겹칠 경우 낮은 값을 가진 상어가 이긴다.

해당 문제를 해결할 때 냄새를 업데이트한다면 시간이 많이 걸릴 것이라 생각했기에 time으로 그냥 계산해 준다.

해당 문제에서 26 퍼에서 틀린다면 1000 이상 인지 초과인지  개발 순서의 시간을 언제 업데이트

하는지 확인해야 한다. 

#include<iostream>
#include<vector>

using namespace std;
static const int SharkBasic_Mover[4][2] = { {0,-1} ,{0,1}, {-1,0}, {1,0} };
enum direction {
	UP = 0,
	DOWN,
	LEFT,
	RIGHT
};
struct Shark
{
public:
	Shark() {
		Mover = vector<vector<direction>>(4, vector<direction>(4));
		Sharknumber = -1;
		PosX = -1, PosY = -1;
	}

	vector<vector<direction>> Mover;
	direction dir;
	int PosX, PosY, Sharknumber;
	bool IS_Alive = true;
};

void AdultShark() {
	//N*N , M개상어, K냄새 남는시간
	int N = 0, M = 0, K = 0, time = 0;
	//현재시간과 비교해서 사라졌는지 확인
	cin >> N >> M >> K;
	vector< Shark>Sharks(M, Shark());
	vector<vector<pair<int, int>>> World(N, vector<pair<int, int>>(N, make_pair(-1, -1)));
	int num = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> num;
			if (num != 0) {
				Sharks[num - 1].PosX = j;
				Sharks[num - 1].PosY = i;
				Sharks[num - 1].Sharknumber = num - 1;
				World[j][i] = make_pair(num - 1, time);

			}
		}
	}
	//상어방향
	for (int i = 0; i < M; ++i) {
		cin >> num;
		Sharks[i].dir = direction(num - 1);
	}
	//방향우선순위
	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < 4; ++j) {
			for (int k = 0; k < 4; ++k) {
				cin >> num;
				Sharks[i].Mover[j][k] = direction(num - 1);
			}
		}
	}
	vector<direction>* MoveDir;
	int x = 0, y = 0;
	while (M != 1)
	{
		time++;
		//이동할 위치 넣기
		for (Shark& S : Sharks) {
			if (S.IS_Alive == false) continue;
			//move
			MoveDir = &(S.Mover[S.dir]);
			direction nowdir = S.dir;
			int Smellx = -1, Smelly = -1;
			bool ISMove = false;
			for (int i = 0; i < MoveDir->size(); ++i) {

				x = S.PosX + SharkBasic_Mover[(int)((*MoveDir)[i])][0];
				y = S.PosY + SharkBasic_Mover[(int)((*MoveDir)[i])][1];
				if (x < 0 || N <= x || y < 0 || N <= y)continue;
				if (World[x][y].first == -1) {
					S.dir = (*MoveDir)[i];
					S.PosX = x;
					S.PosY = y;
					ISMove = true;
					break;
				}
				else {
					// 현재 -   기록 시간       유지시간
					if (((time - World[x][y].second) > K)) { //  (3time - 1) 2냄새 지남 
						//빈칸취급
						S.dir = (*MoveDir)[i];
						S.PosX = x;
						S.PosY = y;
						ISMove = true;
						break;
					}//                                              선턴
					else if (World[x][y].first == S.Sharknumber && Smellx == -1) {
						Smellx = x;
						Smelly = y;
						nowdir = (*MoveDir)[i];
					}
				}
			}
			//냄새칸 첫위치
			if (ISMove == false) {
				S.PosX = Smellx;
				S.PosY = Smelly;
				S.dir = nowdir;
			}
		}


		for (int i = 0 ; i < Sharks.size();++i)
		{
			Shark& S = Sharks[i];
			if (S.IS_Alive == false) continue;

			if (World[S.PosX][S.PosY].second == time) {
				S.IS_Alive = false;
				M--;
			}
			else
			{
				World[S.PosX][S.PosY] = make_pair(S.Sharknumber, time);
			}
		}

		if (time > 1000) { time = -1; break; }
	}
	cout << time;
}

int main() {


	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	AdultShark();
}

알고리즘 문제 코드 수정후 재빌드 상태에서 강제 취소 했을때

LNK1136 에러가 났다 

해당 에러는 빌드시 불러오는 헤더에서 문제가 생긴것으로 추측하고있다.

디버그 돌려도 해결되지않는다.

다시 빌드 시 문제가 해결된다.

ctrl +, 또는 ctrl + t  전체 페이지중 이동

ctrl +. :빠른작업  리팩토링

ctrl +j :  자동완성 표시

ctrl + r +r : 함수나 변수 명을 한번에 변경

ctrl + k +d : 줄 자동 정렬

ctrl + k +c  : 주석 으로 변경

ctrl + k + u : 주석 해제 - 하나씩 해제

ctrl + m + o :  정의 부분만 보이기

f12 : 정의 탐색

shift +f12 : 모든 참조 찾기

디버그 중 중단점이후

f11 : 한단계씩 코드 실행 - 함수내부까지 들어감

f10 : 프로시저  단위 실행

cpp 로 백준 문제를 풀다보면 여러가지 팁을 얻을수 있는데

그중에 해당 코드를 볼수있는데

std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);

해당 코드들은 cpp 입출력 성능을 최적화 하기위해 사용되는 설정들이다.

std::ios::sync_with_stdio(false);

는 cpp iostream 과 c의 stdio 를 동기화 하는 설정을 해제한다.

기본적으로 cpp는 c의 printf scanf 등과 호환성을위해 동기화 되어있다.

동기화를 해제하면 cin과 cout 속도가 빨라지지만 printf scanf 와 같이쓸수없다.

std::cin.tie(0); 또는std::cin.tie(nullptr); 

cin과 out의 묶음을 해제한다

기본적으로 cin을 사용하기 전에 cout 버퍼를 flush 하는 동작이 묶여있는데 이를 해제한다.

입력받기전에 출력 버퍼를 비울필요가 없어져서 속도가 향상된다.

std::cout.tie(0) 또는 std::cout.tie(nullptr)

cout의 tie를 해제한다.

cin.tie(0)와 비슷한역활이다.

tie는 cpp의 입출력 스트림에서 두스트림을 묶어주는 역활을 하는데

cout<<"반가워"

cin>>name;

은  내부적으로 사이에 cout.flush 가들어간다. 

하지만 tie(0)을 해서 해제하면 사이에 flush없이 바로 입력을 받는다.

#include<iostream>
using namespace std;


int SugarSalt()
{
	int data = 0,answer=0;
	cin >> data;

	while (data!=0)
	{
		if (data % 5 == 0) {
			data -= 5;
			answer++;
		}
		else if (data - 3 >= 0) {
			data -= 3;
			answer++;
		}
		else {
			answer = -1;
			break;
		}
	}
	return answer;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin.tie(NULL);
	cout<<SugarSalt();

	return 0;
}

해당문제는 그래프  최소 스패닝 트리로 풀 수 있는 문제다.

최소 스패닝트리는 프림과 크루스칼 알고리즘 으로 플수있다.

해당문제는  프림으로 풀었다 프림이 기본적인 알고리즘은 더 쉽다.

간단하게 말하자면  다익스트라가 누적과 다음노드로 가는 가격을 본다면

프림의 경우는 현재 갈 수 있는 간선들 중 가장 값싼 간선을 우선적으로 본다는 것이다,.

다시 문제로 돌아와

"켜져 있는"위치로만 가야 하기에 다익스트라는 다시 왔을 때 가격을 비교해야 하기에 어울리지 않을 수 있다.

코드르 보면서 설명해 보자

#include<iostream>
#include <queue>
#include<tuple>
#include<vector>
#include <unordered_map>
using namespace std;
unordered_map<int, vector<pair<int, int>>> Spninmap;
unordered_map<int, bool> maps;
//unordered_map<int, int> sp_map;
int gagungchi = 0;
int k = 0;
priorityqueue<pair<int, int>> q;
void minSpningTree() {
    int a = 0, b = 0;
    int n = 0, m = 0, v = 0;
    while (true)
    {
        Spninmap = *new unordered_map<int, vector<pair<int, int>>>();
        maps = *new unordered_map<int, bool>();
        gagungchi = 0;
        k = 0;
        cin >> a >> b;
        if (a == 0 && b == 0) return;
        //그래프로 섬들을 만들어준다.
        for (int i = 0; i < b; i++) {
            cin >> n >> m >> v;
            Spninmap[n].push_back(make_pair(-v, m));
            Spninmap[m].push_back(makepair(-v, n));
            k += v;
        }
        //시작위치 n 으로 잡고 갈수있는 간선들을 받아준다.
        for (auto i : Spninmap[n]) {
            q.push(i);
        }
        //현재위치 탐색완료
        maps[n] = true;
        while (!q.empty())
        {
            auto c = q.top();
            q.pop();
            if (maps[c.second] == true) continue;
            maps[c.second] = true;
            //전력 업데이트
            gagungchi += -(c.first);
            //현재 갈수있는 간선들 추가
            for (auto i : Spninmap[c.second]) {
            //갔던섬이면 빼주기
                if (maps[i.second] == true) continue;
                q.push(i);
            }
        }
        cout << k - gagungchi<<"\n";
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin.tie(NULL);
    minSpningTree();
    return 0;
}

종이 자르기 문제

위처럼 종이가 주어지면 흰색 부분과 파란 부분을 분리하여 자르되

정사각형이 되도록  자르는게 목적이다.

해당 문제는 한칸씩 확인하며 정사각형을 측정한다면

틀렸을때 최적이 될 정사각형을 찾아야 하기에

중복 되는 탐색이 매우 많을 것 같은 느낌이다.

이문제는 모든 사각형을 정사각형으로 자른다가 핵심이라고 생각한다.

가장 큰 종이에서 나올 수 있는 최대 정 사각형은 4개 그 안에서도 4개로 오히려 쪼개면서 계산하는 것이다.

사실 문제에서 내용을 이미지로 간단하게 설명해준다.

위 이미지 순서대로 큰거 자르고 문제 있는 부분만 자르면서 들어가는식으로 풀면된다

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> arrya;
int color[2] = {0,0};

//재귀함수
void Recursive(int size, int x, int y) {
	int  a = arrya[x][y];
	bool is_same = false;
	
    //해당 크기의 정사각형 완전탐색하며 문제있는지 확인
    for (int i = x; i < x + size; i++) {
		for (int j = y; j < y + size; j++) {
			if (arrya[i][j] != a)
			{
				is_same =true;
				break;
			}
		}
		if (is_same)break;
	}
    //정사각형 4개로 나눠서 재귀
	if (is_same) {
		size /= 2;
		Recursive(size, x, y);
		Recursive(size, x + size, y);
		Recursive(size, x, y + size);
		Recursive(size, x + size, y + size);
	}
	else {
    //다채워졌다면 사각형이니 +1
		color[a]++;
	}





}



void solution() {
	int size;
	cin >> size;
	arrya = vector<vector<int>>(size);

	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			int z = 0;
			cin >> z;
			arrya[i].push_back(z);
		}
	}
	Recursive((size ), 0, 0);
	cout << color[0] << "\n"<<color[1];




}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);


	solution();
	return 0;
}

알고리즘의 기초 중 기초? 라고 볼수있는 flood fill 알고리즘을 알아보자

위키백과 에선 플러드필 혹은 시드필 이라고 명명다.

내생각엔 알고리즘 의 기본 내용은 정말 간단하다

영역을 탐색하고 조건에 맞게 채우면 끝이다.

위키백과에서 설명하는 gif 다.

https://en.wikipedia.org/wiki/File:Recursive_Flood_Fill_4_(aka).gif

4방향 상하좌우 만 순서대로 탐색하며 DFS로 재귀함수를 사용해서 탐색하였을때 위 gif 처럼 차오른다.

enum EMap
{
	Wall,
	Empty,
	Fill
};


// 현재위치에서 이동할 방향
int NextMover[4][2] = { {0,-1} ,{-1,0} ,{1,0},{0,1} };

//채우기 알고리즘 DFS
void FloodFill(vector<vector<EMap>>& map, int x, int y)
{
// 현재 위치 채워주기
	map[x][y] = EMap::Fill;
    
	for (const auto* Move : NextMover) {
	
    	int movex = x + Move[0],
			movey = y + Move[1];
	    //방향 이 배열을 나가지 않는지 확인
    	if (movex <0 || movex >= map.size() || movey < 0 || movey >= map[0].size()) continue;
	    //만약 비워져있다면 탐색 시작
    	if (map[movex][movey] == EMap::Empty) {
			FloodFill(map, movex, movey);
		}
	}

}


vector<string> images = { "■","□","◆"};


int main() {
	vector<vector<EMap>> VectorMap = {
		 {Empty,Empty,Empty,Empty,Empty}
		,{Empty,Empty,Empty,Empty,Empty}
		,{Empty,Empty,Empty,Empty,Empty}
		,{Empty,Empty,Empty,Wall,Wall}
		,{Empty,Empty,Empty,Wall,Empty} };

	for (int i = 0; i < VectorMap.size(); ++i) {
		for (int j = 0; j < VectorMap[0].size(); ++j) {
			cout << images[VectorMap[i][j]] << " ";
		}
		cout << "\n";
	}


	int PlayerX = 0, PlayerY = 0;
	FloodFill(VectorMap, PlayerX, PlayerY);

	for (int i = 0; i < VectorMap.size(); ++i) {
		for (int j = 0; j < VectorMap[0].size(); ++j) {
			cout << images[VectorMap[i][j]] << " ";
		}
		cout << "\n";
	}
}​

컴퓨터 그래픽스나 이미지 처리에서 특정 영역을 채우는 데 사용되는 알고리즘이다.

페인트 프로그램에서 특정 픽셀을 클릭했을 때 해당 색상을 기준으로 연결된 영역 전체를 새로운 색으로

채우는 기능에 사용할수있다

해당 알고리즘에서는 채우는게 목적이지만

BFS나 DFS 탐색으로 같은 영역을 탐색하는건 다른 알고리즘에서도 정말 많이쓰인다.

일전에 작성했던 석유시추 역시 BFS로 탐색하며 해당 영역을 찾아낸다.

간단하고 기초적인 알고리즘이지만 정말 많이 쓰인다.

https://programing-note.tistory.com/entry/%EC%84%9D%EC%9C%A0%EC%8B%9C%EC%B6%94-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4LV2

글쓴이는 일전에 다이렉트 x11로 땅따먹기 게임을 만들때 처음 사용했다.