191018 백준 알고리즘 문제풀기

|

[13458] 시험 감독

  • 난이도: 하
    • 문제의 난이도 자체는 어렵지 않았다.
    • 문제의 이해부터 구현까지 40분정도 소요되었다.
    • 수의 입출력 부분때문에 많은 시간을 낭비했다.
    • 또한 문제의 조건이 명확하지 않아서 시간이 많이 낭비됐다.
    • 그리고 while문을 이용해 계속 빼는식으로 매 칸 인원을 줄여나가 시간초과가 떳다.
      • 이는 간단하게 나누기를 해서 해결 가능한 문제였지만 당시엔 쉽게 떠오르지 않았다.
  • 문제
    • https://www.acmicpc.net/problem/13458
    • 총 N개의 시험장이 있고, 각 칸에는 응시자 수가 주어진다.
    • 각 시험장에는 총감독관 1명, 부감독관 여러명이 있다.
      • 총감독관은 1명만 필수로 있어야 하고, 부감독관은 상관없다.
    • 다음으로 인원수 B, C가 주어질 때, B는 총감독관 커버 인원수, C는 부감독관 커버 인원수를 의미한다.
    • 응시장 상태가 주어질 때 최소 필요 감독관 수를 출력한다.
  • 풀이
    • 입력을 받는다.
    • 매 칸마다 총감독관 인원수를 뺀다.
      • 이 때, 빼진 수가 음수가 될 경우 그냥 넘어가야 한다!
    • 매 칸 남은 수는 부감독관 인원수로 나눈다.
      • 나머지가 존재할 경우, 나눈 수+1을 한다.
    • 최솟값을 비교해 저장한다.
    • 항상 입출력 수의 크기를 고려해야 할 듯 하다..
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <vector>

#define MAX 2147483647

using namespace std;

vector<int> A;

int main()
{
	int N;
	scanf("%d", &N);
	int input;
	
	while (N--)
	{
		scanf("%d", &input);
		A.push_back(input);
	}
	long long B, C;
	scanf("%lld %lld", &B, &C);
	long long ans = 0;
	int length = int(A.size());
	
	for (int i = 0; i < length; i++)
	{
		A[i] -= B;
		ans++;
		if (A[i] < 0) continue;
		long long div = A[i] / C;
		long long rest = A[i] % C;
		if (rest != 0) div++;
		ans += div;
	}

	printf("%lld\n", ans);

	//std::system("pause");
	return 0;
}

[2146] 다리 만들기

  • 난이도: 중
    • 문제 자체는 크게 어렵지 않았다.
    • 문제를 읽자마지 풀이가 바로 떠올랐고, 생각대로 푸니 바로 맞았다.
      • 총 푸는데 1시간도 소요되지 않았다.
    • BFS를 이용해 섬을 그룹짓고, 다른 섬으로 가야하는 가장자리 정보들을 따로 저장한다음에 브루트포스처럼 모든 경우의 수를 비교해 최솟값을 찾는다.
    • 다리를 하나만 놓으면 되서 비교적 쉽게 풀린 듯 하다.
  • 문제
    • https://www.acmicpc.net/problem/2146
    • 크기 N(100이하)의 맵이 주어지고, 0은 바다, 1은 육지를 나타낸다.
    • 항상 두 개 이사으이 섬이 있는 데이터만 입력으로 주어질 때, 가장 짧은 다리 하나를 놓을 때의 다리 길이를 구한다.
    • 문제를 나누면
      • 입력을 받고
      • 섬을 그룹짓고
        • 섬을 그룹지으면서 가장자리 좌표들을 저장한다음
      • 모든 가장자리 좌표들에 대해 다른 섬을 만날때까지 BFS로 탐색한다.
      • 다른 섬을 만나면 다리가 완성된것으로 최솟값을 찾는다.
  • 풀이
    • 입력을 받고
    • 섬을 그룹짓는다
      • 전체 맵에서 육지를 찾고, 해당 육지는 섬 번호로 check 맵을 모두 초기화한다.
        • 이 때, nx와 ny가 육지에서 바다로 변하는 순간의 cx, cy는 다리가 시작될 수 있는 부분으로 edge에 따로 저장한다.
      • 현재 섬을 BFS로 모두 탐색했으면 섬 번호를 1 증가시키고 다시 새로운 육지를 탐색한다.
    • 모든 가장자리 좌표에서 다리를 만든다.
      • 섬 번호가 다 메겨졌으면, 다시 BFS를 이용해 다리를 만들기 시작한다.
      • 만약 다음 좌표인 nx, by 자리가 같은 섬이거나 방문했던적이라면 넘어가고, 다음 섬을 찾았다면 최소 거리를 구한다음 초기화한다.
        • 해당 좌표 check 값이 최소 거리가 될 것이다.
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>
#include <cstring>
#define MAX 2147483647

using namespace std;

struct info
{
	int x, y, unum;
};

int map[101][101];
int unions[101][101];
int check[101][101];

int answer = MAX;

vector<info> edges;

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

int main()
{
	int N;
	scanf("%d", &N);
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &map[j][i]);
		}
	}

	int edges_idx = 0;
	edges.push_back({ -1,-1,-1 });

	//섬 그룹짓기
	int cnt_union = 1;
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			if (map[j][i] == 0) continue; // 현재자리 바다라면 넘어가고
			if (unions[j][i] != 0) continue; // 현재자리 번호가 메겨졌다면 넘어간다.
			queue<pair<int, int>> q;
			unions[j][i] = cnt_union; // 위 조건을 모두 통과했으면 현재자리부터 탐색 시작.
			q.push(make_pair(i, j));
			while (!q.empty())
			{
				int cx = q.front().first;
				int cy = q.front().second;
				q.pop();
				for (int k = 0; k < 4; k++)
				{
					int nx = cx + dx[k];
					int ny = cy + dy[k];
					if (nx < 0 || N <= nx || ny < 0 || N <= ny) continue;
					if (map[ny][nx] == 0 && map[cy][cx] == 1)
					{//가장자리 부분이라면
						if (edges[edges_idx].x != cx || edges[edges_idx].y != cy)
						{//현재좌표와 이전좌표 다르다면 가장자리 좌표와 팀 뽑기
            // 이는 현재좌표 cx, cy 기준으로 nx, ny를 찾기때문에 cx,cy의 중복을 방지하기 위함이다.
            // edges_idx는 바로 전 인덱스를 가리킨다.
							edges.push_back({ cx,cy,cnt_union });
							edges_idx++;
						}
					}
					else
					{//가장자리 부분이 아니라면 
						if (unions[ny][nx] != 0) continue;
						unions[ny][nx] = cnt_union;
						q.push(make_pair(nx, ny));
					}
				}
			}
			cnt_union++;
		}
	}

	// 다른 섬 찾아가기

	for (int i = 1; i<int(edges.size()); i++)
	{
		memset(&check, 0, sizeof(check));
		queue<tuple<int, int, int>> q;
		int cx = edges[i].x;
		int cy = edges[i].y;
		int cu = edges[i].unum;
		check[cy][cx] = 1;
		q.push(make_tuple(cx, cy, cu));
		while (!q.empty())
		{
			tie(cx, cy, cu) = q.front();
			q.pop();
			for (int k = 0; k < 4; k++)
			{
				int nx = cx + dx[k];
				int ny = cy + dy[k];
				if (nx < 0 || N <= nx || ny < 0 || N <= ny) continue; // 범위 벗어나면 넘어감
				if (check[ny][nx] != 0) continue; // 방문했던적 넘어감
				if (unions[ny][nx] == cu) continue; // 같은 섬도 넘어감
				check[ny][nx] = check[cy][cx] + 1;
				q.push(make_tuple(nx, ny, cu));
				if (cu != unions[ny][nx] && unions[ny][nx] != 0)
				{//만약 다음 섬을 찾았다면
					//현재거리: check[cy][cx]
					if (check[cy][cx] < answer) answer = check[cy][cx]; // 최소 거리 초기화
				}
			}
		}
	}

	printf("%d\n", answer - 1);

	//std::system("pause");
	return 0;
}

[17471] 게리맨더링

  • 난이도: 상
    • 상당히.. 어려웠다.
    • 문제를 이해하는데 10분, 풀이를 떠올리는데 30분, 구현 1시간, 나머지 디버깅으로 푸는데 총 3시간정도 걸린듯 하다.
    • 일반적인 2차원 BFS만 주구장창 하다가 갑자기 맞닥뜨린 1차원 BFS에 살짝 멘붕이 왔다.
      • 일반적인 그래프 문제..
      • 어려운게 아니지만 익숙치 않다보니 상당히 어렵게 느껴졌다.
      • 몇번 더 봐야할듯..
  • 문제
    • https://www.acmicpc.net/problem/17471
    • 첫째 줄에 전체 구역의 개수 N, 둘째 줄에 각 구역 1번부터 N번까지 인원 수, 셋째 줄 부터 N째줄 동안 1번부터 N번까지 해당 노드와 연결된 노드 정보가 주어진다.
    • 그룹은 항상 두개로 나뉘어야 하며, 한 그룹엔 최소 한 개의 노드를 갖는다.
    • 전체 노드들을 두 그룹으로 나눈다.
    • 나눠진 두 그룹의 모든 노드들은 서로 연결 되어있어야 한다.
    • 나눠진 두 그룹 내의 인원수들을 모두 합한 뒤, 두 그룹 사이의 인원 수 최소 차이를 출력한다.
    • 문제를 나누면
      • 입력을 받는다.
      • 두 그룹을 나눈다.
      • 나눠진 두 그룹의 유효성을 검사한다.
        • 모든 노드는 서로 연결되어 있는지 확인한다.
      • 만약 나뉜 그룹이 유효하다면 노드 내 인원수를 계산하고 최솟값을 찾는다.
  • 풀이
    • 입력을 받는다.
    • 두 그룹을 나눈다.
      • 일반적인 DFS 알고리즘을 이용해 재귀적으로 나눌 수 있다.
      • 나눌 때는 꼭 한 그룹에는 최소 한 노드가 있어야 한다.
      • 따라서 전체 N개의 노드에 대해 1개부터 N/2개까지의 경우만 따지면 된다.
        • 어차피 그 이상은 또 반복이니까..
    • 나눠진 두 그룹의 유효성을 검사한다.
      • 1차원 BFS를 이용한다.
      • 첫 번째 그룹의 첫 번째 노드에서 연결된 노드들을 모두 check 한다.
        • 이 때, 연결된 노드들이 다른 그룹에 속해있으면 check 하지 않는다
      • 이런식으로 한 그룹의 전체 노드들에 대한 check 맵을 만든다.
      • 만약 check 맵에 한 그룹의 어떤 노드 하나가 check 되어있지 않다면, 그 노드는 연결되어 있는 상태가 아니다.
        • 따라서 유효하지 않은 그룹이다.
      • 만약 두 노드가 모두 유효하다면 다음으로 넘어간다.
    • 나뉜 그룹 내 인원수와 최솟값 계산
      • 그냥 인원수만큼 더한담에 서로 뺀 값의 최솟값을 구한다.(절댓값)
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#define MAX 2147483647

using namespace std;

struct info
{
	int members, group;
};

vector<info> town; // 그룹별 사람수, 선택여부
vector<int> connect[11]; // 그룹별 연결관계

int check[11]; // 체크 맵

int answer = MAX;

bool checker(int a, vector<int> group)
{//a가 group 안에있으면 true, 없으면 false 반환
	bool answer = false;
	for (int i = 0; i<int(group.size()); i++)
	{
		if (a == group[i])
		{
			answer = true;
			break;
		}
	}
	return answer;
}

bool validator(int N, vector<int> check_group, vector<int> other_group)
{ // check 그룹이 유효하면 true, 유효하지 않으면 false 반환
	memset(&check, 0, sizeof(check)); // check 초기화

	queue<int> q;
	// 체크 그룹 첫번째 숫자 체크한다음 BFS
	check[check_group[0]] = 1;
	q.push(check_group[0]);
	while (!q.empty())
	{
		int c = q.front();
		q.pop();
		for (int i = 0; i < connect[c].size(); i++)
		{ // 현재 노드와 연결된 노드들동안
			int n = connect[c][i]; // 다음 숫자는 체크 숫자와 연결된 노드
			if (checker(n, other_group)) continue; //만약 다음 숫자 n이 다른 그룹에 있으면 넘어간다.
			if (check[n] != 0) continue; //다음 숫자 체크되어있으면 넘어간다.
			check[n] = 1; // 모두 만족한다면 체크한다.
			q.push(n);
		}
	}

	bool answer = true;
	for (int i = 0; i<int(check_group.size()); i++)
	{
		if (check[check_group[i]] != 1)
		{ // 만약 해당 그룹 숫자가 체크가 되어있지 않다면 연결된게 아니다.
			answer = false; // 따라서 false
		}
	}

	return answer;
}

void calc(int N, int num)
{
	vector<int> group_a; // 해당 그룹 숫자 담기
	vector<int> group_b;
	for (int i = 0; i<int(town.size()); i++)
	{
		if (town[i].group == 1) group_a.push_back(i + 1);
		else group_b.push_back(i + 1);
	}

	//생성된 그룹 유효성 검사
	//그룹 유효성 검사
	if (validator(N, group_a, group_b) && validator(N, group_b, group_a))
	{//두 그룹 모두 유효한 그룹이라면
		//그룹 a의 합
		int sum_a = 0;
		for (int i = 0; i<int(group_a.size()); i++)
		{
			sum_a += town[group_a[i] - 1].members;
		}
		//그룹 b의 합
		int sum_b = 0;
		for (int i = 0; i<int(group_b.size()); i++)
		{
			sum_b += town[group_b[i] - 1].members;
		}
		int dif = abs(sum_a - sum_b); // 절댓값 차
		if (dif < answer) answer = dif; // 최솟값 비교
	}
	return;
}

void dfs(int idx, int cnt, int N, int num)
{
	if (cnt == num)
	{
		// 골라진 노드들은 group=1로 초기화되어있음
		calc(N, num);
		
		return;
	}
	for (int i = idx; i < N; i++)
	{ // 현재 인덱스부터 총 N까지 돈다.
		if (town[i].group == 1)continue; // 만약 선택되어있다면 넘어간다.
		town[i].group = 1; //선택하고
		dfs(i + 1, cnt + 1, N, num); // 다음 번째 부터 참조한다.(중복방지)
		town[i].group = 0; //선택해제
	}
}

int main()
{
	int N;
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		int temp;
		scanf("%d", &temp);
		town.push_back({ temp,0 });
	}
	for (int i = 1; i <= N; i++)
	{
		int nums;
		scanf("%d", &nums);
		for (int j = 0; j < nums; j++)
		{
			int temp;
			scanf("%d", &temp);
			connect[i].push_back(temp);
		}
	}

	for (int n_group = 1; n_group <= int(N / 2); n_group++)
	{
		//고르기 및 연산
		dfs(0, 0, N, n_group);
	}

	if (answer == MAX) answer = -1; // 못 나누는 경우 -1 출력
	printf("%d\n", answer);

	//std::system("pause");
	return 0;
}

191017 백준 알고리즘 문제풀기

|

[15683] 감시

  • 난이도: 극상상!
    • 문제 이해하는데는 10분도 걸리지 않았지만, 구현+디버깅하는데 3~4시간이 넘게 소요된듯 하다.
      • 처음에 전체 맵에 대해 모든 경우의 수를 구하도록 했더니 worst case 기분 연산까지 1분이 넘게 소모된다.
    • DFS의 이용에 대해 익숙하지 않아서 이렇게 오래 걸린듯 하다.
    • DFS를 조금 더 응용할 수 있는 능력을 길러야 할 듯 하다.
      • DFS는 모든 경우의 수를 찾을 때(완전탐색) 굉장히 유용한 알고리즘이다.
      • 함수를 재귀적으로 구성하고, 어떤 조건을 만족했을 때 해당 재귀를 끝내고 연산을 시작하게 만들 수 있다.
    • 개인적으로 풀어본 문제 중 가장 공부가 많이 되었던 문제인것 같다.
      • 나중에 복습해야할듯.
    • 특히, 모든 카메라의 경우의 수를 고려할 때 2차원 배열로 해서 각각 위치에 가능한 카메라들을 할당하고 접근하여 풀게 했더니 무조건 시간초과가 나는 결과를 초래했다.
      • Worst case 기준 1분이 넘어가도 경우의 수가 계산되지 않음..
    • 연구소 문제같은 경우는 2차원 배열 안에서 벽을 선택하면 되지만, 이런 문제는 그런식으로 접근하면 무조건 시간초과가 발생한다.
    • 이런식으로 어떠한 큰 배열(Map) 안에 특정 점의 소수의 상태(Camera)가 주어지는 경우, 맵에서 모든 경우의 수를 찾는게 아니라 Camera에서 모든 경우의 수를 찾아야 한다.
    • 중요한 타입의 문제 같으니 꼭 다시한번 봐야할듯..
  • 문제
    • https://www.acmicpc.net/problem/15683
    • 입력으로 N, M, N열 M행의 맵의 주어질 때, 카메라의 사각지대가 최소가 될 때의 사각지대 크기를 구한다.
    • 맵이 입력되고, 카메라는 1~5, 벽은 6으로 주어진다.
    • 카메라끼리 보는 영역은 중첩될 수 있다. 단, 카메라는 통과 할 수 있지만 벽은 통과하지 못한다.
    • 카메라는 각각 90도씩 회전 가능하며, 아래 영역을 한번에 본다.
      1. 한 방향
      2. 좌, 우
      3. 상, 우
      4. 좌, 상, 우
      5. 네 방향
    • 모든 경우의 수를 구해 사각지대를 계산한다.
  • 풀이
    • 문제를 나누면
      • 입력을 받고
      • 모든 경우의 수를 찾은다음에
      • 찾아진 각 경우의 수에 대해 카메라가 보는 영역을 만들고
      • 사각지대를 계산해서
      • 최솟값을 저장한다.
    • 가장 중요한 부분은 모든 경우의 수를 찾는 부분이다.
      • DFS를 이용해서 모든 경우의 수를 찾는다.
      • 각 카메라는 1, 3, 4는 4가지의 경우의 수, 2는 2가지, 5는 1가지의 경우의 수가 있다.
      • 이에 맞게 각각 최대 경우의 수를 설정하고(각각 숫자는 방향을 의미하도록!)
      • 해당 카메라가 고를 수 있는 방향의 경우의 수 중 방향을 정하고
      • 다음 카메라로 넘어가 또 방향의 경우의 수 중 방향을 정한다.
      • 만약 모든 카메라를 다 정했으면 경우의 수를 구한것이므로 연산을 시작한다.
      • 자세한건 밑에 코드에…
    • 카메라 방향을 정했으면, 카메라가 보는 영역을 만든다.
      • 간단하게 while문으로 카메라의 어떤 방향으로만 참조하는 함수를 만들고 호출해 완성
    • 사각지대를 계산
      • 전체 맵에서 카메라, 벽은 세지 않는다.
      • 이에 근거해 빈 칸(0)을 세면 된다.
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <vector>
#include <tuple>

#define MAX 2147483647

using namespace std;

struct camera
{
	int x, y, type;
};

int map[9][9]; // 맵 저장
int chosen_dir[9][9]; // 선택된 방향
int calc_map[9][9]; // 계산용 맵
vector<camera> cams;

int dx[] = { 0, 1,0,-1,0 }; // 1, 2, 3, 4 index는
int dy[] = { 0, 0,1,0,-1 }; // 우, 하, 좌, 상 순서

int num_cams = 0;
int answer = MAX;

void init_calcmap(int h, int w)
{ // 계산용 맵을 초기화한다.
	for (int j = 0; j < h; j++)
	{
		for (int i = 0; i < w; i++)
		{
			calc_map[j][i] = chosen_dir[j][i];
		}
	}
}

void viewer(int h, int w, int nx, int ny, int dir)
{ // 해당 방향으로 끝날때까지 check한다.
	while (1)
	{
		nx += dx[dir];
		ny += dy[dir];
		if (nx < 0 || w <= nx || ny < 0 || h <= ny) break; // 범위 벗어나면 끝
		if (map[ny][nx] == 6) break; // 벽 나오면 끝
		calc_map[ny][nx] = 1;
	}
	return;
}

void view_map(int h, int w, int cx, int cy, int type, int dir)
{ // 카메라의 종류에 따라 맵을 완성시킨다.
	int nx = cx;
	int ny = cy;
	if (type == 1)
	{
		calc_map[cy][cx] = 1; // 현재위치 찍고
		viewer(h, w, nx, ny, dir); // 본다.
	}
	else if (type == 2)
	{// 2번 방향 좌우
		calc_map[cy][cx] = 1; // 현재위치 찍고
		if (dir == 1)
		{// 좌우 1, 3
			viewer(h, w, nx, ny, 1);
			viewer(h, w, nx, ny, 3);
		}
		if (dir == 2)
		{// 상하 4, 2
			viewer(h, w, nx, ny, 4);
			viewer(h, w, nx, ny, 2);
		}
	}
	else if (type == 3)
	{// 3번 방향 상우
		calc_map[cy][cx] = 1; // 현재위치 찍고
		if (dir == 1)
		{// 상우 4, 1
			viewer(h, w, nx, ny, 4);
			viewer(h, w, nx, ny, 1);
		}
		if (dir == 2)
		{// 우하 1, 2
			viewer(h, w, nx, ny, 1);
			viewer(h, w, nx, ny, 2);

		}
		if (dir == 3)
		{// 하좌 2, 3
			viewer(h, w, nx, ny, 2);
			viewer(h, w, nx, ny, 3);
		}
		if (dir == 4)
		{// 좌상 3, 4
			viewer(h, w, nx, ny, 3);
			viewer(h, w, nx, ny, 4);
		}
	}
	else if (type == 4)
	{// 4번 방향 좌상우
		calc_map[cy][cx] = 1; // 현재위치 찍고
		if (dir == 1)
		{// 좌상우 3, 4, 1
			viewer(h, w, nx, ny, 3);
			viewer(h, w, nx, ny, 4);
			viewer(h, w, nx, ny, 1);
		}
		if (dir == 2)
		{// 상우하 4, 1, 2
			viewer(h, w, nx, ny, 4);
			viewer(h, w, nx, ny, 1);
			viewer(h, w, nx, ny, 2);
		}
		if (dir == 3)
		{// 우하좌 1, 2, 3
			viewer(h, w, nx, ny, 1);
			viewer(h, w, nx, ny, 2);
			viewer(h, w, nx, ny, 3);
		}
		if (dir == 4)
		{// 하좌상 2, 3, 4
			viewer(h, w, nx, ny, 2);
			viewer(h, w, nx, ny, 3);
			viewer(h, w, nx, ny, 4);
		}
	}
	else //(type == 5)
	{
		calc_map[cy][cx] = 1; // 현재위치 찍고
		//4방향
		for (int i = 1; i < 5; i++)
		{
			viewer(h, w, nx, ny, i);
		}
	}
	return;
}

void calc(int h, int w)
{
	// 사각지대 만들기
	for (int i = 0; i < num_cams; i++)
	{//카메라들 동안
		int cx = cams[i].x;
		int cy = cams[i].y;
		int type = cams[i].type;
		int cd = chosen_dir[cy][cx];
		view_map(h, w, cx, cy, type, cd); // 현재 카메라가 보는 맵 만들기.
	}

	// 사각지대 세기
	int cnt = 0;
	for (int j = 0; j < h; j++)
	{
		for (int i = 0; i < w; i++)
		{
			if (map[j][i] == 0)
			{//카메라 감시 가능한 구간만
				if (calc_map[j][i] == 0)
				{//사각지대 세기
					cnt++;
				}
			}
		}
	}
	//정답 비교
	if (cnt < answer) answer = cnt;
}

void dfs(int h, int w, int cnt)
{
	if (cnt == num_cams)
	{// 마지막 카메라까지 방향을 골랐으면
		init_calcmap(h, w); // 계산용 맵 초기화하고
		calc(h, w); // 계산을 시작한다.
		return;
	}
	//가능한 카메라 기본 방향은 4방향으로 하고
	int dir_cnt = 4;
	if (map[cams[cnt].y][cams[cnt].x] == 2) dir_cnt = 2; // 2번카메라는 2방향
	if (map[cams[cnt].y][cams[cnt].x] == 5) dir_cnt = 1; // 5번카메라는 1방향
	for (int i = 1; i <= dir_cnt; i++)
	{//모든 카메라 방향동안
		chosen_dir[cams[cnt].y][cams[cnt].x] = i;//현재 순번 카메라 좌표의 방향을 찍고
		dfs(h, w, cnt + 1); //다음 카메라로 넘어간다.
	}

}

int main()
{
	int N, M;
	scanf("%d %d", &N, &M);
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < M; i++)
		{
			scanf("%d", &map[j][i]);
			if (map[j][i] != 0 && map[j][i] != 6)
			{//카메라라면
				cams.push_back({ i,j,map[j][i] }); // 카메라들 저장
				//x, y, type, dir
			}
		}
	}
	//카메라 개수 세고
	num_cams = cams.size();
	//경우의 수 만들기 시작
	dfs(N, M, 0);

	//정답
	printf("%d\n", answer);

	//std::system("pause");
	return 0;
}

[17142] 연구소 3

  • 난이도: 극상!
    • 풀었던 문제를 실패서 다시 풀었다. 성공하도록 풀어봤다.
    • 전체 경우의 수를 구하는 부분을 공부하기 아주 좋은 문제인듯 하다.
    • 이미 풀었던 문제기에 처음부터 푸는데 1시간 반정도 걸린듯 하다.
  • 문제
    • https://www.acmicpc.net/problem/17142
    • 맵 가로세로 크기 N, 활성화 바이러스 개수 M개, 맵에 주어지고 M개의 바이러스를 활성화시켜 전체 연구소를 덮는 최소시간을 구하는 문제
    • 문제를 나누면
      • 바이러스 고르기
      • 바이러스 퍼치기
    • 이렇게 나뉘지만, 바이러스 고르는게 제일 관건인 문제다.
    • 특이한것은, 활성화 되지 않은 바이러스라도 바이러스가 존재하는것으로 간주해야 한다.
  • 풀이
    • 바이러스 고르기
      • DFS 알고리즘을 이용한다.
      • 바이러스를 고르는데는, 첫 번째 바이러스부터 전체 바이러스 동안 DFS를 이용해 활성화->DFS 재귀->비활성화 순을 따르면 된다.
      • 하지만 중요한것은
        • 다음 DFS 접근 시 해당 인덱스부터 시작하도록 해야 중복되는 경우를 방지할 수 있다.
        • 예를 들어 말하면
          • 5개 바이러스중 3개를 고르는 경우의 수는 5C3으로 5.4.3/3.2.1 로 총 10가지의 경우의 수다.
          • 만약 0번째 인덱스부터 매 번을 고르게 되면 고른 수를 나열하는 5P3이 되므로 60가지로 늘어난다.
          • 이를 처리하지 못해 시간초과가 발생했었다.
      • 자세한건 밑에 코드에서 설명..
    • 바이러스 퍼치기
      • 일반적인 BFS 알고리즘을 이용한다.
      • 다만, 비활성화 바이러스가 존재하는것은 이미 바이러스가 있는것이다.
      • 따라서 다음 위치가 비활성화 바이러스라면 다음위치에서 바이러스 퍼치기가 불가능할 경우 counting 하지 않아야 한다.
        • 이미 바이러스가 존재하므로 counting하면 중복 counting이 된다.
        • 문제 페이지의 첫 번째 test case를 해결하는 방법이다.
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

#define MAX 2147483647

using namespace std;

struct virus
{
	int x, y, activate; // 각각 좌표와 활성화 여부를 저장한다.
};

int map[51][51]; // 맵 저장용
int calc_map[51][51]; // 계산맵 저장용

int dx[] = { -1,1,0,0 }; // 이동방향
int dy[] = { 0,0,-1,1 };

vector<virus> viruses; // 바이러스 정보 저장
int num_virus = 0; // 활성화 바이러스 개수

int answer = MAX;

void spread(int N)
{// 바이러스 퍼치기
	//맵 초기화
	memset(&calc_map, 0, sizeof(calc_map)); // 계산맵을 초기화하고
	
	queue<pair<int, int>> q;
	
	for (int i = 0; i<int(viruses.size()); i++)
	{//전체 바이러스 중
		//활성화 바이러스 우선 활성화해서 큐에 넣는다.
		if (viruses[i].activate == 0) continue;
		calc_map[viruses[i].y][viruses[i].x] = 1;
		q.push(make_pair(viruses[i].x, viruses[i].y));
	}
	// 활성화바이러스들부터 먼저 탐색을 시작해야 전체적으로 매 초마다 고르게 퍼져간다.
	// 그렇지 않으면 첫 번째 바이러스가 끝날때까지 무조건 다 돌게되어 올바르지 않게 동작한다!
	
	while (!q.empty())
	{
		int cx = q.front().first;
		int cy = q.front().second;
		q.pop();
		for (int k = 0; k < 4; k++)
		{
			int nx = cx + dx[k];
			int ny = cy + dy[k];
			if (nx < 0 || N <= nx || ny < 0 || N <= ny) continue; // 범위 벗어나면 지나감
			if (map[ny][nx] == 1) continue; // 벽 만나면 지나감
			if (calc_map[ny][nx] != 0) continue; // 방문한적 있음 지나감
			if (map[ny][nx] == 2)
			{//만약 다음이 비활성화 바이러스라면
				int cnt = 0;
				for (int t = 0; t < 4; t++)
				{
					int tx = nx + dx[t];
					int ty = ny + dy[t];
					if (tx < 0 || N <= tx || ty < 0 || N <= ty) continue; // 범위 벗어나면 지나감
					if (map[ty][tx] == 1) continue; // 벽 만나면 지나감
					if (calc_map[ty][tx] != 0) continue; // 방문한적 있음 지나감
					//갈 데가 있으면 count
					cnt++;
				}
				if (cnt == 0)
				{//갈 곳이 한군데도 없다면 check만 한다.
				// check만 하는게 비활성화를 활성화 상태로 만드는것이다.
				// 어차피 비활성화 상태 바이러스도 바이러스이므로 다음에 퍼지지 않는다면
				// 시간이 소요되면 안되므로 예외처리한다.
					calc_map[ny][nx] = calc_map[cy][cx];
				}
				else
				{//갈 곳이 있으면 다음 부분으로 퍼치기 위해 시간이 소요되며 퍼진다.
					calc_map[ny][nx] = calc_map[cy][cx] + 1;
					q.push(make_pair(nx, ny));
				}
			}
			else
			{//만약 다음이 비활성화 바이러스가 아니라면 그냥 퍼진다.
				calc_map[ny][nx] = calc_map[cy][cx] + 1;
				q.push(make_pair(nx, ny));
			}
				
		}
	}

	// 바이러스 최대 시간 찾기
	int maxval = -1;
	bool iszero = false;
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			if (map[j][i] == 1) continue;//벽은 넘어가고
			if (calc_map[j][i] == 0)
			{// 0이 있다면 계산하나 마나니까 빠져나감
				iszero = true;
				break;
			}
			if (maxval < calc_map[j][i])
			{//맵에서 최댓값 찾고
				maxval = calc_map[j][i];
			}
		}
	}
	if (iszero == false && maxval < answer)
	{
		answer = maxval;
	}
}

void dfs(int N, int idx, int cnt)
{ // index 번째 바이러스부터 시작해서 활성화 바이러스를 다 고른다음 퍼친다.
	if (cnt == num_virus)
	{//활성화 바이러스를 다 골랐으므로
		spread(N); // 퍼친다.
		return;
	}
	// 인덱스는 idx번째부터 시작한다.
	// 그래야 중복선택되는것을 막을 수 있다.
	// 즉, 해당 idx번째가 골라졌을때 계산 가능한 경우의 수는 모두 구해졌기에
	// 다음부터 볼 필요 없으므로 idx로 초기화한다.
	for (int i = idx; i < int(viruses.size()); i++)
	{//전체 바이러스들에 대해
		if (viruses[i].activate == 0)
		{// 활성화 되지 않았다면
			viruses[i].activate = 1; // 해당 바이러스 활성화 시키고
			dfs(N, i + 1,cnt + 1); // 여기가 핵심!!
			// 현재 인덱스 다음 바이러스부터 고려하면 된다.
			viruses[i].activate = 0; // 다시 비활성화 한다.
		}
	}
}

int main()
{
	int N, M;
	scanf("%d %d", &N, &M);
	int wall_cnt = 0;
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &map[j][i]);
			if (map[j][i] == 2) viruses.push_back({ i,j,0 });
			if (map[j][i] == 1) wall_cnt++;
		}
	}
	num_virus = M;

	if ((wall_cnt + int(viruses.size())) == (N*N))
	{// 전체 맵에 비활성화 바이러스로 다 찬 경우, 이미 바이러스가 다 찬 상태이므로 0초 소요되는게 맞다.
		printf("%d\n", 0);
	}
	else
	{// 아닌 경우라면 연산을 수행
		//바이러스 선택하기
		dfs(N, 0, 0);

		if (answer == MAX) answer = -1;
		else answer -= 1;
		printf("%d\n", answer);
	}

	//std::system("pause");
	return 0;
}
  • DFS와 BFS를 능수능란하게 다뤄야 하는 어려운 문제다.
    • DFS를 이용한 모든 경우의 수를 고려하는 부분에 대한 연습이 많이 필요한듯 하다.

[15686] 치킨 배달

  • 난이도: 중상
    • 문제를 이해하고, 예제 손으로 풀어보고, 문제를 작게 나누고, 풀이를 떠올리는데 30분
    • 1차적으로 구현하는데 30분 해서 총 1시간만에 정답을 맞췄다.
    • 하지만 시간초과가 떴으며, 비효율적인 접근방법과 문제를 살짝 잘못이해해서 수정하는데 추가 30분정도 더 걸렸다.
      • 각 집과 치킨집까지의 거리를 처음엔 BFS로 찾았지만, 쓸데없는 짓이었다. 그냥 좌표끼리 빼서 절댓값을 씌우면 그게 최소거리다.
        • 중간에 장애물이 있는 경우엔 BFS로 푸는게 맞지만, 이렇게 장애물이 없는경우엔 그냥 절댓값 차를 이용하면 된다.
    • 앞에서 다뤘던 DFS로 모든 경우의 수를 찾는 문제를 연습 할 수 있어서 좋았다.
  • 문제
    • https://www.acmicpc.net/problem/15686
    • NxN 크기의 도시는 1크기의 칸으로 나뉘고, 각 자리는 빈칸(0), 집(1), 치킨집(2)로 나뉜다.
    • 각 집부터 치킨집까지의 최소거리(제일 가까운곳)를 치킨 거리라고 한다.
    • 모든 치킨 거리를 더했을 때 이를 도시의 치킨 거리라고 한다.
    • 입력으로 주어지는 M 숫자와 도시 맵에서 최대 M개의 치킨집 을 남겼을 때, 도시의 치킨 거리의 최솟값을 출력한다.
      • 즉, 1개부터 M개까지의 치킨집을 모두 test 해 봐야 한다.
    • 문제를 나누면
      • 입력을 받고
      • 정해진 개수의 치킨집을 고른다음에(1개부터 M개까지)
      • 골라진 치킨집을 이용해 각 집과의 치킨 거리를 계산하고
      • 도시의 치킨 거리를 구하고 최솟값을 저장한다.
  • 풀이
    • 입력을 받고
      • 입력은 배열을 이용했지만, 전체 맵에 대해 집 좌표와 치킨집 좌표를 저장해 활용한다.
      • 속도를 빠르게 할 수 있다.
    • 정해진 개수의 치킨집을 고른다.
      • 고르는 치킨집 개수는 for문을 이용해 1개부터 M개까지 고르도록 함수 인자로 넘긴다.
      • 앞의 문제들처럼 DFS를 이용해 푼다.
        • DFS의 인자로 현재 index와 카운팅 개수, 목적 개수(고르는 치킨집 개수)를 받는다.
        • 만약 카운팅 개수가 목적 개수와 같아진다면 치킨집을 다 골랐으므로 치킨거리를 계산한다.
        • 카운팅 개수가 부족하다면 현재 인덱스 다음 인덱스를 DFS에 집어넣어 재귀호출을 실행한다.
    • 골라진 치킨집을 이용해 각 집과의 치킨 거리 계산
      • 저장된 집 위치에서 골라진 치킨집 위치끼리의 거리를 모두 계산하고 최솟값을 받아 저장한다.
      • 거리는 각 좌표간 절댓값 차를 이용한다.
    • 도시의 치킨 거리를 구하고 최솟값을 저장
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>

#define MAX 2147483647

using namespace std;

struct info
{
	int x, y, chosen;
};

int map[51][51];

vector<info> chicken;
vector<info> houses;

int answer = MAX;

void calc_distance(int N)
{
	int distances = 0;

	for (int i = 0; i<int(houses.size()); i++)
	{
		int min_dist = MAX;
		for (int k = 0; k<int(chicken.size()); k++)
		{// 치킨집까지의 거리중 최솟값을 저장
			if (chicken[k].chosen != 1) continue;
			int dist = abs(houses[i].x - chicken[k].x) + abs(houses[i].y - chicken[k].y);
			if (dist < min_dist) min_dist = dist;
		}
		distances += min_dist;
	}
	if (distances < answer) answer = distances; // 최솟값 저장
}

void dfs(int idx, int cnt, int num_chicken, int N)
{
	if (cnt == num_chicken)
	{
		calc_distance(N);
		return;
	}

	for (int i = idx; i<int(chicken.size()); i++)
	{//전체 치킨집동안
		if (chicken[i].chosen == 1) continue; // 골라졌으면 넘어간다.
		chicken[i].chosen = 1; // 고르고
		dfs(i + 1, cnt + 1, num_chicken, N); // 다음 인덱스로 넘겨 들어간다.(중복 방지)
		chicken[i].chosen = 0; // 고르기 해제
	}
}


int main()
{
	int N, M;
	scanf("%d %d", &N, &M);

	//입력받기
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &map[j][i]);
			if (map[j][i] == 2) chicken.push_back({ i,j,0 });
			if (map[j][i] == 1)	houses.push_back({ i,j,-1 });
		}
	}

	for (int idx = 1; idx <= M; idx++)
	{// idx = 골라지는 치킨집 갯수
		dfs(0, 0, idx, N);
	}

	printf("%d\n", answer);

	//std::system("pause");
	return 0;
}

191016 백준 알고리즘 문제풀기

|

[16234] 인구 이동

  • 난이도: 중
    • 문제 이해 및 풀이 떠올리는데 30분, 구현 + 디버깅 해서 1시간 좀 안되게 소요
      • 총 80분정도 걸림
    • 처음엔 어렵겠다 생각했지만, 테스트 케이스를 이해한대로 하나한 풀어보며 문제를 완벽하게 이해할 수 있었다.
      • 반드시 문제를 100프로 이해하고 풀기 시작해야 한다!
    • BFS를 이용해서 비교적 쉽게 풀 수 있었다.
  • 문제
    • https://www.acmicpc.net/problem/16234
    • 처음에 N, L, R, NxN 크기의 맵이 주어진다.
      • N은 지도 가로세로 크기, L은 최소인원차, R은 최대인원차
    • 어떠한 국가는 1x1 칸 하나에 존재하며, 상하좌우 인접 국가와 인원차이가 L이상, R이하일 때 국경을 연다
      • 국경을 여는것은 같은 union으로 일단 묶은다음, 한번에 국경을 열어 인원들을 이동시킨다.
    • 같은 연합끼리 서로 국경이 열리면 모든 인원은 평균값으로 초기화된다. (소수 버림)
    • 만약 더 이상 인구 이동이 일어날 수 없으면 종료한다.
    • 총 인구이동이 몇 번 일어났는지를 출력한다.
  • 풀이
    • 문제를 쪼개보면
      • 입력을 받고
      • 입력 받은 맵에서 인구이동이 가능한 union끼리 묶고
        • 만약 이전 인구 이동 union과 현재 union이 같다면 종료
        • 더 이상 인구이동이 불가하므로
      • 인구를 이동시키고 국경을 닫는다.
      • 더 이상 인구이동이 불가할때까지 무한반복.
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstring>

using namespace std;

int map[51][51]; // 인구맵
int c_union[51][51]; // 현재 연합
int p_union[51][51]; // 이전 연합

int dx[] = { -1,1,0,0 }; // 이동 방향
int dy[] = { 0,0,-1,1 };

// worst case 기준으로 배열 선언
int union_members[51 * 51]; // 해당 연합의 인원수
int union_cnts[51 * 51]; // 해당 연합의 국가수

bool open_wall(int cx, int cy, int nx, int ny, int L, int R)
{ // 조건을 만족하면 국경을 연다.
	int diff = abs(map[cy][cx] - map[ny][nx]);
	if (L <= diff && diff <= R) return true;
	else return false;
}

int main()
{
	int N, L, R;
	scanf("%d %d %d", &N, &L, &R);
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &map[j][i]);
		}
	}

	int move = 0;

	while (1)
	{
		//연합을 나누고
		int union_cnt = 1;
		for (int j = 0; j < N; j++)
		{
			for (int i = 0; i < N; i++)
			{
				//모든 국가 중 union이 구분되었다면 넘어간다.
				if (c_union[j][i] != 0) continue;
				queue <pair<int, int>> q;
				c_union[j][i] = union_cnt;
				q.push(make_pair(i, j));
				while (!q.empty())
				{
					int cx = q.front().first;
					int cy = q.front().second;
					q.pop();
					for (int k = 0; k < 4; k++)
					{
						int nx = cx + dx[k];
						int ny = cy + dy[k];
						// 다음 국가 선택 범위 벗어나면 넘어간다.
						if (nx < 0 || N <= nx || ny < 0 || N <= ny) continue;
						// 다음 국가가 분류 되어있다면 넘어간다.
						if (c_union[ny][nx] != 0) continue;
						//만약 벽을 열 수 있다면
            if (open_wall(cx, cy, nx, ny, L, R))
						{
							c_union[ny][nx] = union_cnt; // 같은 연합으로.
							q.push(make_pair(nx, ny));
						}
					}

				}
				union_cnt++; // 현재 연결된 모든 연합을 찾아 연결했으므로 다음으로 넘어간다.
			}
		}

		//연합을 비교해서 이전 연합과 같으면 종료
		int temp = 0;
		for (int j = 0; j < N; j++)
		{
			for (int i = 0; i < N; i++)
			{
				if (c_union[j][i] == p_union[j][i]) temp++;
			}
		}
		if (temp == N * N) break;

		//나눠진 연합 내에서 인구수 구한담에
		for (int j = 0; j < N; j++)
		{
			for (int i = 0; i < N; i++)
			{
				union_members[c_union[j][i]] += map[j][i]; // 해당 국가의 연합에 인원수 더하고
				union_cnts[c_union[j][i]]++; // 해당 union 인원수 계산
			}
		}

		//평균 인원수 구하고
		for (int i = 0; i < N*N; i++)
		{
      //만약 인원 없는 연합이라면 넘어간다.
			if (union_members[i] == 0) continue;
			union_members[i] = int(union_members[i] / union_cnts[i]);
		}

		//map에서 인구이동
		for (int j = 0; j < N; j++)
		{
			for (int i = 0; i < N; i++)
			{
				map[j][i] = union_members[c_union[j][i]]; // 인구 이동
				p_union[j][i] = c_union[j][i]; // 비교를 위해 이전 연합 저장
				c_union[j][i] = 0; // c_union 초기화
			}
		}
    move++; // 인구 이동 횟수 센다.
		
    //변수 초기화
		memset(union_members, 0, sizeof(union_members));
		memset(union_cnts, 0, sizeof(union_cnts));
	}

	printf("%d\n", move - 1); // while문의 중간에 현재 연합을 구하고 비교해 빠져나오므로 1을 뺀 값이 정답이 된다.

	//std::system("pause");
	return 0;
}

191015 백준 알고리즘 문제풀기

|

[16235] 나무 재테크

  • 난이도: 상
    • 문제 이해 30분, 구현하는데 40분, 디버깅 1시간정도 걸렸다.
    • 결국 시간 복잡도때문에 틀렸다.
    • 아무래도 우선순위 큐를 사용하다보니 늦어졌고, 게다가 이중 for문으로 하나하나 좌표단위로 접근하다보니 틀린듯 하다.
    • 모든 문제는 풀기에 앞서 정확하게 조건을 이해하고, 정리하고, 직접 어떻게 되는지 손으로 풀어보고 이해한다음에 풀기 시작하면 못 풀 문제는 없을것이라 생각한다..
    • 하지만 맞게 풀었다고 무조건 맞는것도 아닌듯하다 ㅠㅠ
      • 시간복잡도..
    • 만약 시험에 나왔으면 시간복잡도때문에 틀렸다.
  • 문제
    • https://www.acmicpc.net/problem/16235
    • 정사각형 맵의 크기 N, 나무의 개수 M, 햇수 K가 순서대로 입력됨
    • 다음으로, 각 맵에 매 해 겨울 줄 비료상태가 입력됨
    • 마지막으로 M개의 나무 좌표와 나무 나이가 입력 됨
    • 조건
      • 한 칸에는 여러개의 나무가 존재 할 수 있다.
        • 이게 핵심 조건
      • 가장 처음 땅에 있는 양분은 모두 5다.
      • 봄에는
        • 자신 나이만큼 나무가 양분을 먹고 나이가 1 증가한다.
        • 자신이 존재하는 칸의 양분만 섭취 가능하다.
        • 한 칸에 여러 나무가 존재시, 나이 어린 나무부터 양분을 섭취한다.
        • 만약 땅에 양분이 부족해 나이만큼 양분을 먹지 못하면 즉시 사망한다.
      • 여름에는
        • 봄에 죽은 나무가 양분이 된다.
        • 양분이 되는 죽은 나무는 나이를 2로 나눈 값이 해당 칸의 양분으로 더해진다.(소숫점 버림)
      • 가을에는
        • 나무가 번식한다.
        • 나이가 5의 배수일 때만 번식한다.
        • 땅 범위를 벗어나는 번식은 하지 않는다.
        • 인접한 8개 칸에 나이 1인 나무가 새로 생성된다.
      • 겨울에는
        • 땅에 로봇이 양분을 추가한다.
        • 추가되는 양분은 위에서 비료상태로 입력된다.
  • 풀이
    • 우선순위 큐 이용
      • 우선순위 큐는 큐에 새로 입력되는 데이터가 어떠한 정렬 순서에 따라 정렬되어 자기 자리를 찾아간다.
      • C++ STL에서는 <queue>에서 제공된다.
        • priority_queue<data_type, container<data_type>, order<data_type>> pq_name
          • ex. priority_queue<int, vector<int>, greater<int>> pq
          • greater 규칙을 따르면 가장 작은 값이 pq.top()에 존재한다.
          • 반대로 less 규칙을 따르면 가장 큰 값이 pq.top()에 존재한다.
    • 우선순위 큐를 2차원 배열 형태로 이용한다면 시간초과로 문제가 틀린다.
      • 아래 코드는 틀린 문제 풀이 코드(정답은 맞지만 시간조건을 초과함)
      • 다양한 방법으로 for문을 최소화해봤지만 소용없다.
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

int biryo[11][11];
int dead[11][11];
int curmap[11][11];

int dx[] = { 0,1,1,1,0,-1,-1,-1 };
int dy[] = { -1,-1,0,1,1,1,0,-1 };

priority_queue<int, vector<int>, greater<int>> c_tree[11][11]; // 작은게 맨 위로
priority_queue<int, vector<int>, greater<int>> n_tree[11][11];

void init_curmap(int N)
{
	for (int j = 1; j <= N; j++)
	{
		for (int i = 1; i <= N; i++)
		{
			curmap[j][i] = 5;
		}
	}
}

int main()
{
	int N, M, K;
	scanf("%d %d %d", &N, &M, &K);
	
	//비료맵 저장
	for (int j = 1; j <= N; j++)
	{
		for (int i = 1; i <= N; i++)
		{
			scanf("%d", &biryo[i][j]);
		}
	}

	//나무 저장
	for (int i = 0; i < M; i++)
	{
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		c_tree[y][x].push(z);
	} // c_tree에는 해당 좌표에 나무 크기가 순서대로 저장됨


	int year = K;
	// 맵 초기화
	init_curmap(N);

	while (year--)
	{//년수동안
		//봄
		for (int j = 1; j <= N; j++)
		{
			for (int i = 1; i <= N; i++)
			{
				if (c_tree[j][i].size() != 0)
				{// 현재 위치 나무가 존재한다면
					while (!c_tree[j][i].empty())
					{//현재 위치 나무들동안 나이가 어린 나무부터
						int cur_size = c_tree[j][i].top();
						c_tree[j][i].pop(); // 현재 나무를 뽑아서
						if (curmap[j][i] >= cur_size)
						{//만약 해당 위치 양분이 현재 나이보다 많다면
							curmap[j][i] -= cur_size; // 양분 먹고
							n_tree[j][i].push(cur_size + 1); // 나이 1 증가해서 다음 맵에저장
							continue;
						}
						else
						{//해당 위치 양분이 나이보다 부족하다면
							dead[j][i] += int(cur_size / 2); // 죽은 나무가 되어 반 크기의 양분이 됨
						}
					}
				}

				//여름, 겨울 비료주기
				curmap[j][i] += dead[j][i];
				curmap[j][i] += biryo[j][i];
				dead[j][i] = 0; // dead 초기화

			}
		}
		////여름, 겨울(비료 주기)
		//for (int j = 1; j <= N; j++)
		//{
		//	for (int i = 1; i <= N; i++)
		//	{
		//		//죽은 나무는 양분이 된다.
		//		curmap[j][i] += dead[j][i];
		//		curmap[j][i] += biryo[j][i];
		//		dead[j][i] = 0; // dead 초기화
		//	}
		//}
		//가을 (나무 번식)
		for (int j = 1; j <= N; j++)
		{
			for (int i = 1; i <= N; i++)
			{
				if (n_tree[j][i].size() != 0)
				{// 만약 현재위치 나무가 존재한다면
					while (!n_tree[j][i].empty())
					{// 현재위치 나무들동안
						int cur_size = n_tree[j][i].top(); // 현재 나무 크기 저장
						n_tree[j][i].pop(); // 현재 나무 뽑고
						if (cur_size % 5 == 0)
						{//만약 현재 나무가 번식조건이라면(5의 배수)
							for (int k = 0; k < 8; k++)
							{
								int nx = i + dx[k]; // 다음위치 찾고
								int ny = j + dy[k];
								if (nx < 1 || N < nx||ny < 1 || N < ny) continue; // 범위 안이라면
								c_tree[ny][nx].push(1); // 현재 맵의 다음 위치에 번식
							}
							c_tree[j][i].push(cur_size); // 현재 맵에 현재 나무 옮겨심기
						}
						else
						{//만약 나무가 번식조건이 아니라면
							c_tree[j][i].push(cur_size); // 다음 맵에 나무를 옮겨심는다
						}
					}
				}
			}
		}
		//겨울 비료주기는 여름에
	}

	// 나무 개수 세기
	int cnt = 0;
	for (int j = 1; j <= N; j++)
	{
		for (int i = 1; i <= N; i++)
		{
			if (c_tree[j][i].size() != 0)
			{//나무 있으면
				while (!c_tree[j][i].empty())
				{//나무들을
					c_tree[j][i].pop();//뽑고
					cnt++; //센다.
				}
			}
		}
	}

	printf("%d\n", cnt);
	//std::system("pause");
	return 0;
}
  • 이 문제를 덱을 이용해서 풀면 다음과 같다
    • 덱을 이용하면 시간초과 문제를 해결 할 수 있고(sorting 없으니까) 문제를 통과할 수 있다.
    • 문제에서 입력으로 주어지는 나무의 위치는 모두 서로 다름 조건을 잘 고민해보면 덱으로 풀 수 있는 문제라는 힌트를 얻을 수 있었다.
      • 문제를 꼼꼼히 읽는게 최고의 방법인듯 하다.
    • 덱은 앞에서 자료를 넣고 빼고, 뒤에서 넣고 빼고 할 수 있다.
    • 위 코드에서 우선순위 큐를 덱으로만 바꾸고 중간에 코드 살짝만 바꾸면 된다.
      • 어떠한 좌표에서 나무 나이가 작은 값이 맨 오른쪽으로, 큰 값이 맨 왼쪽으로 가야한다.
      • 덱에서 새로 생성되는 나무들은 무조근 크기가 작으니까 push_back으로 넣으면 된다.
      • 2 개의 덱을 번갈아가며 사용하기 때문에, 새로 생성되는 나무는 무조건 오른쪽(back)에서 넣고, 기존 나무는 왼쪽(front)에서 넣으면 순서는 항상 바뀔 수 없다.
        • pop은 무조건 back에서만, push는 새 나무는 back, 큰 나무는 front에서 push!
        • 이 순서만 지키면 무조건 순서는 정렬되어있게 된다.
    • 자세한건 밑에 코드 참조
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>

using namespace std;

int biryo[11][11];
int dead[11][11];
int curmap[11][11];

int dx[] = { 0,1,1,1,0,-1,-1,-1 };
int dy[] = { -1,-1,0,1,1,1,0,-1 };

deque<int> c_tree[11][11];
deque<int> n_tree[11][11];

int main()
{
	int N, M, K;
	scanf("%d %d %d", &N, &M, &K);

	//비료맵 저장
	for (int j = 1; j <= N; j++)
	{
		for (int i = 1; i <= N; i++)
		{
			scanf("%d", &biryo[i][j]);
			curmap[j][i] = 5; // 처음 비료 초기화
		}
	}

	//나무 저장
	for (int i = 0; i < M; i++)
	{
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		c_tree[y][x].push_front(z); // 일단은 그냥 순서 상관없이 집어넣는다. 어차피 입력되는 나무의 위치는 모두 다르니까.
	} // c_tree에는 해당 좌표에 나무 크기가 저장

	int year = K;

	while (year--)
	{//년수동안
	 //봄
		for (int j = 1; j <= N; j++)
		{
			for (int i = 1; i <= N; i++)
			{
				if (c_tree[j][i].size() != 0)
				{// 현재 위치 나무가 존재한다면
					while (!c_tree[j][i].empty())
					{//현재 위치 나무들동안
						int cur_size = c_tree[j][i].back(); // 뒤쪽에서 어린 나무부터 뽑아낸다.
						c_tree[j][i].pop_back();
						if (curmap[j][i] >= cur_size)
						{//만약 해당 위치 양분이 현재 나이보다 많다면
							curmap[j][i] -= cur_size; // 양분 먹고
							n_tree[j][i].push_front(cur_size + 1); // 나이 1 증가해서 다음 맵에 앞으로 집어넣는다.
							continue;
						}
						else
						{//해당 위치 양분이 나이보다 부족하다면
							dead[j][i] += int(cur_size / 2); // 죽은 나무가 되어 반 크기의 양분이 됨
						}
					}
				}

				//여름, 겨울 비료주기
				curmap[j][i] += dead[j][i];
				curmap[j][i] += biryo[j][i];
				dead[j][i] = 0; // dead 초기화

			}
		}
		
		//가을 (나무 번식)
		for (int j = 1; j <= N; j++)
		{
			for (int i = 1; i <= N; i++)
			{
				if (n_tree[j][i].size() != 0)
				{// 만약 현재위치 나무가 존재한다면
					while (!n_tree[j][i].empty())
					{// 현재위치 나무들동안
						int cur_size = n_tree[j][i].back(); // 가장 작은 나무부터
						n_tree[j][i].pop_back(); // 현재 나무 뽑고
						if (cur_size % 5 == 0)
						{//만약 현재 나무가 번식조건이라면(5의 배수)
							for (int k = 0; k < 8; k++)
							{
								int nx = i + dx[k]; // 다음위치 찾고
								int ny = j + dy[k];
								if (nx < 1 || N < nx || ny < 1 || N < ny) continue; // 범위 안이라면
								c_tree[ny][nx].push_back(1); // 현재 맵의 다음 위치에 번식
							}// 나무 번식은 무조건 제일 작은 나무 크기이므로 덱의 뒤에서 집어넣는다.
							c_tree[j][i].push_front(cur_size); // 현재 맵에 현재 나무 옮겨심기
						}// 현재 나무는 무조건 큰 나무일 것이므로 덱 앞에 집어넣는다.
						else
						{//만약 나무가 번식조건이 아니라면
							c_tree[j][i].push_front(cur_size); // 그냥 다음 맵에 나무를 옮겨심는다(앞으로 넣어야 함)
						}
					}
				}
			}
		}
		//겨울 비료주기는 여름에 완료
	}

	// 나무 개수 세기
	int cnt = 0;
	for (int j = 1; j <= N; j++)
	{
		for (int i = 1; i <= N; i++)
		{
			cnt += c_tree[j][i].size(); // 해당 위치 사이즈가 곧 나무 갯수이므로
		}
	}

	printf("%d\n", cnt);

	//std::system("pause");
	return 0;
}
  • 쉬운줄 알고 덤벼보면 문제는 꼭 항상 어렵다.

191014 백준 알고리즘 문제풀기

|

[17142] 연구소 3

  • 난이도: 상
  • 문제 풀이 떠올리는데 30분, 구현까지 1시간 걸렸지만 디버깅만 주구장창 하다가 결국 틀렸다.
  • 시간 초과
  • 너무 조건이 많아 어렵다
  • 특히, 바이러스를 퍼치는 부분이 정말 까다로웠다.
  • 제일 중요한것은 문제를 정확하게 이해하고 풀기 시작하는 것 같다.
  • 정확하기 이해하기 전부터 풀기 시작하다보니 결국 산으로 간다…

  • 문제
    • https://www.acmicpc.net/problem/17142
    • NxN 크기 맵이 주어진다.
    • 맵에서 바이러스들이 2, 벽이 1, 공간이 0으로 주어지며, 임의의 바이러스 M개를 골라 전체 맵에 퍼칠 경우 걸리는 최소시간을 출력.
    • 맵에는 바이러스들이 활성/비활성 상태로 존재하며, M개의 바이러스만 골라 활성화 상태로 바꾼다.
    • 활성화 상태가 된 바이러스는 상, 하, 좌, 우로 1초에 1칸씩 퍼져나간다.
    • 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다
      • 표현이 조금 애매해서 이해하는데 한참 걸렸다.
      • 그러니까, 바이러스가 퍼지는 칸에는 비활성 바이러스가 있건 없건 상관이 없다.
      • 모든 칸에 퍼지는 시간을 구하는것이 문제였다. 따라서 비활성 바이러스도 바이러스로 쳐야 한다.
        • 문제 자체를 __모든 칸에 활성 바이러스를 퍼치는데 걸리는 시간__으로 이해해서 한참 헤멧다.
        • 비활성 바이러스는 활성화 되지 않아도 바이러스다..
  • 풀이
    • 문제를 나누면
      • 상태 맵을 입력 받는다.
      • 활성화 시킬 바이러스 3개를 고르고
      • BFS를 이용해 바이러스를 퍼친다.
        • 다만, 1초에 1칸씩 퍼지므로 이에 유의해서 BFS를 정의해야 한다.
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <queue>

#define MAX 2147483647

using namespace std;

int map[51][51];
int check[51][51];
int calcmap[51][51];

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

int answer = MAX;

int emptycnt = 0;

void init_calcmap(int N, queue<pair<int,int>> &virus)
{
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			calcmap[j][i] = check[j][i];
			if (calcmap[j][i] == -2)
			{//만약 바이러스 위치라면
				calcmap[j][i] = 1;
				virus.push(make_pair(i, j));
			}
			if (calcmap[j][i] != 1 && map[j][i] == 2)
			{//만약 비활성화 바이러스라면 -3으로 초기화
				calcmap[j][i] = -3;
			}
		}
	}
}

void spread_virus(int N)
{
	queue<pair<int, int>> virus;
	
	init_calcmap(N, virus);
	
	//int infect = 0;
	//int time = 0;

	while (!virus.empty())
	{
		int cx = virus.front().first;
		int cy = virus.front().second;
		virus.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			//범위 벗어나면 끝
			if (nx < 0 || N <= nx || ny < 0 || N <= ny) continue;

			if (calcmap[ny][nx] == 0)
			{ // 만약 다음 위치 방문한적 없다면
				//time = calcmap[ny][nx] = calcmap[cy][cx] + 1; // 방문한다.
				calcmap[ny][nx] = calcmap[cy][cx] + 1; // 방문한다.
				virus.push(make_pair(nx, ny));
				//infect++;
			}
			if (calcmap[ny][nx] == -3)
			{ // 만약 다음 위치가 비활성화 바이러스라면
			  //만약 주변에 바이러스가 꽉찻다면 
				int cnt = 0;
				for (int k = 0; k < 4; k++)
				{
					int tx = nx + dx[k];
					int ty = ny + dy[k];
					//범위 안에서
					if (tx < 0 || N <= tx || ty < 0 || N <= ty) continue;
					if (calcmap[ty][tx] == 0) cnt++;
				}
				if (cnt == 0)
				{
					//time = calcmap[ny][nx] = calcmap[cy][cx];// 현재상태로 활성화
					calcmap[ny][nx] = calcmap[cy][cx];// 현재상태로 활성화
					virus.push(make_pair(nx, ny));
					//infect++;
				}
				else
				{
					//time = calcmap[ny][nx] = calcmap[cy][cx] + 1; // 활성화
					calcmap[ny][nx] = calcmap[cy][cx] + 1; // 활성화
					virus.push(make_pair(nx, ny));
					//infect++;
				}
			}

		}
	}
	//printf("time: %d, infect: %d\n", time, infect);
	int maxval = -1;
	bool zero = false;

	//최댓값 찾기
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			if (map[j][i] != 2 && calcmap[j][i] == 0)
			{
				zero = true;
				//break;
				return;
			}
			if (maxval < calcmap[j][i])
			{
				maxval = calcmap[j][i];
			}
		}
	}

	if (!zero && maxval < answer)
	{
		answer = maxval;
	}
}

void virus_choose(int N, int M, int cnt)
{
	if (cnt == M)
	{
		spread_virus(N); //바이러스 퍼치기
		return;
	}
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			if (check[j][i] == 0 && map[j][i] == 2)
			{
				check[j][i] = -2; // 바이러스 선택
				virus_choose(N, M, cnt + 1);
				check[j][i] = 0;
			}
		}
	}
}



int main()
{
	int N, M;
	scanf("%d %d", &N, &M);
	int wall = 0;
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &map[j][i]);
			if (map[j][i] == 1)
			{
				check[j][i] = -1;
				wall++;
			}
		}
	}

	//emptycnt = N * N - wall - M;
	//printf("%d\n", emptycnt);

	// 바이러스 고르기
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			if (check[j][i] == 0 && map[j][i] == 2)
			{//바이러스 위치라면
				check[j][i] = -2; // 바이러스 선택
				virus_choose(N, M, 1);
				check[j][i] = 0;
			}
		}
	}

	if (answer == MAX)
	{
		printf("-1\n");
	}
	else
	{
		printf("%d\n", answer - 1);
	}
  
	std::system("pause");
	return 0;
}
  • 퍼 온 간단하게 구현된 코드다…
    • 출처: https://rebas.kr/846 [PROJECT REBAS]
    • 복잡한 알고리즘을 간단하게 구현했다…
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

struct virus {
    int x, y;
};

int a[50][50], dist[50][50];
int n, m, k, ans=1e9;
bool select[10];
vector<virus> v;
queue<virus> q;
const int dx[] = {-1, 0 , 1, 0}, dy[] = {0, 1, 0, -1};

void bfs() {
    int infect=0, times=0;
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y; q.pop(); 
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (a[nx][ny] != 1 && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y]+1;
                if (a[nx][ny] == 0) {
                    infect += 1;
                    times = dist[nx][ny];
                }
                q.push({nx, ny});
            }
        }
    }
    if (infect == k && ans > times) ans = times;
}

void solve(int idx, int cnt, int d) {
    if (cnt == m) {
        memset(dist, -1, sizeof(dist));
        for (int i=0; i<d; i++) {
            if (select[i]) {
                q.push({v[i].x, v[i].y});
                dist[v[i].x][v[i].y] = 0;
            }
        }
        bfs();
        return;
    }
    for (int i=idx; i<d; i++) {
        if (!select[i]) {
            select[i] = true;
            solve(i+1, cnt+1, d);
            select[i] = false;
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            scanf("%d", &a[i][j]);
            if (a[i][j] == 2) v.push_back({i, j});
            if (a[i][j] == 0) k += 1;
        }
    }
    solve(0, 0, v.size());
    printf("%d\n", ans == 1e9 ? -1 : ans);
    return 0;
}