구름톤 챌린지 2st Week (2)

2주차 4번째 문제 - 폭탄 구현하기(2)

#include <iostream>
#include <vector>
#include <sstream>
#include <set>
#include <algorithm>

using namespace std;

int main() {
	int N, K;
	cin >> N >> K;
	cin.ignore();

	set<pair<int, int>> at;
	set<pair<int, int>> sharp;

	vector<vector<int>> result(N, vector<int>(N, 0));

	vector<vector<string>> ground(4);

	string ss;
	string sss;
	for (int i = 0; i < N; i++)
	{
		getline(cin, ss);
		istringstream iss(ss);

		int j = 0;
		while (iss >> sss)
		{
			if (sss == "@")
				at.insert({ i,j });
			else if(sss == "#")
				sharp.insert({ i,j });
			j++;
		}
	}

	int dr[] = { 0, 1, -1, 0, 0 };
	int dc[] = { 0, 0, 0, 1, -1 };

	int r, c;
	while (K > 0) {
		cin >> r >> c;
		r--; c--;

		for (int i = 0; i < 5; i++)
		{

			if (r + dr[i] >= 0 && r + dr[i] < N && c + dc[i] >= 0 && c + dc[i] < N)
			{
				if (at.find({ r + dr[i], c + dc[i] }) != at.end())
					result[r + dr[i]][c + dc[i]] += 2;
				else if (sharp.find({ r + dr[i], c + dc[i] }) != sharp.end())
					continue;
				else
					result[r + dr[i]][c + dc[i]] += 1;

			}
		} 

		K--;
	}

	int maxnum = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			maxnum = max(maxnum, result[i][j]);
	}
	cout << maxnum;

	return 0;
}

폭탄이 떨어진 위치 + 상하좌우의 땅의 폭탄값은 증가한다. 기본 땅이면 +1씩, @땅이면 +2씩, #땅이면 0씩(contnue) 증가한다.

땅 상태를 입력 받으면서 @이면 set<pair<int, int>> at에, # 이면 set<pair<int, int>> sharp에 저장해준다. 

( set의 탐색, 삽입, 삭제에 대한 시간복잡도가 O(logN) )

 

K번 폭탄이 떨어지는데 이에 맞춰 int dr[] = { 0, 1, -1, 0, 0 }; 와 int dc[] = { 0, 0, 0, 1, -1 }; 를 이용하여 떨어진 위치 + 상하좌우를 계산해준다.

이 때 at과 sharp에 있는 좌표값인지 확인해주며 계산한다.

출력값은 max메소드를 이용해 모든 땅을 순회하며 구해주었다.

 

---

2주차 5번째 문제 - GameJam

#include <iostream>
#include <string>
#include <utility>
#include <set>

using namespace std;

string arr1[201][201];
set<pair<int, int>> s1;

string arr2[201][201];
set<pair<int, int>> s2;

int main() {
	int N;
	cin >> N;

	int r1, c1, r2, c2;
	cin >> r1 >> c1 >> r2 >> c2;
	for (int i = 1; i < N + 1; i++)
		for (int j = 1; j < N + 1; j++)
		{
			cin >> arr1[i][j];
			arr2[i][j] = arr1[i][j];
		}

	bool stop = false;
	int cnt1 = 1;
	while (!stop)
	{
		int move;
		string dir;

		move = stoi(arr1[r1][c1].substr(0, arr1[r1][c1].length() - 1));
		dir = arr1[r1][c1].substr(arr1[r1][c1].length() - 1);
		s1.insert({r1, c1});

		if (dir == "U") {
			while (move-- > 0)
			{
				r1--;
				if (r1 < 1)
					r1 = N;

				if (s1.find({ r1, c1 }) != s1.end())
				{
					stop = true;
					break;
				}
				else
				{
					s1.insert({ r1, c1 });
					cnt1++;
				}
			}
		}
		else if (dir == "D")
		{
			while (move-- > 0)
			{
				r1++;
				if (r1 > N)
					r1 = 1;

				if (s1.find({ r1, c1 }) != s1.end())
				{
					stop = true;
					break;
				}
				else
				{
					s1.insert({ r1, c1 });
					cnt1++;
				}
			}
		}
		else if (dir == "L")
		{
			while (move-- > 0)
			{
				c1--;
				if (c1 < 1)
					c1 = N;

				if (s1.find({ r1, c1 }) != s1.end())
				{
					stop = true;
					break;
				}
				else
				{
					s1.insert({ r1, c1 });
					cnt1++;
				}
			}
		}
		else
		{
			while (move-- > 0)
			{
				c1++;
				if (c1 > N)
					c1 = 1;

				if (s1.find({ r1, c1 }) != s1.end())
				{
					stop = true;
					break;
				}
				else
				{
					s1.insert({ r1, c1 });
					cnt1++;
				}
			}
		}
	}

	stop = false;
	int cnt2 = 1;
	while (!stop)
	{
		int move;
		string dir;

		move = stoi(arr2[r2][c2].substr(0, arr2[r2][c2].length() - 1));
		dir = arr2[r2][c2].substr(arr2[r2][c2].length() - 1);
		s2.insert({r2, c2});
		
		if (dir == "U") {
			while (move-- > 0)
			{
				r2--;
				if (r2 < 1)
					r2 = N;

				if (s2.find({ r2, c2 }) != s2.end())
				{
					stop = true;
					break;
				}
				else
				{
					s2.insert({ r2, c2 });
					cnt2++;
				}
			}
		}
		else if (dir == "D")
		{
			while (move-- > 0)
			{
				r2++;
				if (r2 > N)
					r2 = 1;

				if (s2.find({ r2, c2 }) != s2.end())
				{
					stop = true;
					break;
				}
				else
				{
					s2.insert({ r2, c2 });
					cnt2++;
				}
			}
		}
		else if (dir == "L")
		{
			while (move-- > 0)
			{
				c2--;
				if (c2 < 1)
					c2 = N;

				if (s2.find({ r2, c2 }) != s2.end())
				{
					stop = true;
					break;
				}
				else
				{
					s2.insert({ r2, c2 });
					cnt2++;
				}
			}
		}
		else
		{
			while (move-- > 0)
			{
				c2++;
				if (c2 > N)
					c2 = 1;

				if (s2.find({ r2, c2 }) != s2.end())
				{
					stop = true;
					break;
				}
				else
				{
					s2.insert({ r2, c2 });
					cnt2++;
				}
			}
		}
	}
	
	if (cnt1 > cnt2)
		cout << "goorm " << cnt1;
	else
		cout << "player " << cnt2;
	return 0;
}

입력받은 <count><command> 값들을 arr1(구름)과 arr2(플레이어)에 저장해주었다.

1<= count <= N이고 command는 한글자의 문자이기에 substr(0, arr1[r1][c1].length() - 1)과 substr(arr1[r1][c1].length() - 1)로 나누어주었다.

그 후, 구름과 플레이어가 방문한 곳은 set<pair<int, int>> s1과 s2에 저장해가며 방문하는 지점이 s1이나 s2에 있는지 확인하여 있으면 break 하도록 구현하였다. 방문한 곳의 수는 cnt1과 cnt2를 ++ 해주며 구해주었다.