관심이 가는 개발 보물창고

풀이

stack 자료구조를 사용하면 쉽게 해결할 수 있다.

줄이 1 ~ 6이므로 stack을 배열처럼 사용하면 여러 개의 stack 줄이 생기게 된다.

현재 top과 치려고 하는 프렛의 번호를 비교해서 count를 매기면 된다.

치려고 하는 프렛의 번호를 b라고 하면

top() > b 이면,

pop 해주고 count++

top() == b이면,

굳이 손을 다른 프렛으로 옮기지 않아도 되므로 패스

top() < b이면,

push 하고 count++

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

int n, p;
stack<int> st[7];

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

	cin >> n >> p;

	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;

		while (1)
		{
			if (st[a].empty())
			{
				st[a].push(b);
				cnt++;
				break;
			}
			else if (!st[a].empty() && st[a].top() < b)
			{
				st[a].push(b);
				cnt++;
				break;
			}
			else if (!st[a].empty() && st[a].top() == b)
				break;
			else if (!st[a].empty() && st[a].top() > b)
			{
				st[a].pop();
				cnt++;
			}
		}
	}

	cout << cnt << '\n';
	return 0;
}

풀이

이 문제는 그림을 그리면서 살펴봐야 쉽게 풀 수 있다.

아래 그림을 보면,

가장 위에 있는 숫자는 현재 막대기의 수를 의미한다.

아래의 숫자는 현재 레이저로 쐈을 때 절단되는 막대기의 수이다.

여는 괄호가 들어오면 stack에 push 한다.

닫는 괄호가 들어오면 다음과 같이 판단한다.

닫는 괄호 이전의 괄호가 여는 괄호였다면 pop을 하고 나서 정답에 +stack.size()를 해준다.

닫는 괄호 이전의 괄호가 여는 괄호가 아니라면 pop을 하고나서 정답에 +1을 해준다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main()
{
	string s;
	cin >> s;

	stack<char> st;
	int cnt = 0;
	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] == '(')
			st.push(s[i]);
		else
		{
			if (s[i - 1] == '(')
			{
				st.pop();
				cnt += st.size();
			}
			else
			{
				st.pop();
				cnt++;
			}
		}
	}

	cout << cnt << '\n';
	return 0;
}

풀이

문제부터 이해해보자.

핵심은 스택을 이용해서 원하는 숫자를 만들 수 있는지? 아닌지이다.

하나씩 차근차근 진행해보면,

4를 만들기 위해서는 push 4번, pop 1번

+ + + + Stack [1, 2, 3, 4]

+ + + + - Stack [1, 2, 3]

3을 만들기 위해서는 pop 1번

+ + + + - - Stack [1, 2]

6을 만들기 위해서는 push 2번, pop 1번

+ + + + - - + + Stack [1, 2, 5, 6]

+ + + + - - + + - Stack [1, 2, 5]

8을 만들기 위해서는 push 2번, pop 1번

+ + + + - - + + - + + Stack [1, 2, 5, 7, 8]

+ + + + - - + + - + + - Stack [1, 2, 5, 7]

7을 만들기 위해서는 pop 1번

+ + + + - - + + - + + - - Stack [1, 2, 5]

5, 2, 1을 각 각 pop 1번씩만 해주면 해결할 수 있다.

따라서 결과는

+ + + + - - + + - + + - - - - -

구현은

queue에 현재 만들고자 하는 숫자들을 넣어주고,

현재 만들려고 하는 숫자를 stack의 top과 비교하면서 만들 수 있다면 push 하면서 +를 채워나가고

만들지 못한다면 No를 출력하면 된다.

여기서 만들지 못한다는 것은 현재 queue의 front 값과 stack의 top 부분에서

queue.front() < stack.top() 이면 만들지 못하는 것이다.

ret이라는 벡터는 출력을 위한 +, -를 저장하는 공간이다.

#include <iostream>
#include <stack>
#include <queue>
using namespace std;

int n;
stack<int> st;
queue<int> q;
vector<char> ret;
// stack에 push하는 순서는 반드시 오름차순
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		q.push(x);
	}

	int num = 1;
	bool ok = true;
	while (!q.empty())
	{
		int now = q.front();

		if (!st.empty() && st.top() > now)
		{
			ok = false;
			break;
		}
		if (st.empty())
		{
			st.push(num++);
			ret.push_back('+');
		}
		else
		{
			if (st.top() == now)
			{
				st.pop();
				ret.push_back('-');
				q.pop();
			}
			else
			{
				st.push(num++);
				ret.push_back('+');
			}
		}
	}

	if (ok)
	{
		for (int i = 0; i < ret.size(); i++)
			cout << ret[i] << '\n';
	}
	else
		cout << "NO\n";

	return 0;
}

풀이

맵에서 울타리 '#'가 아닌 지역을 시작점으로 탐색을 해서 양과 늑대의 수를 체크한다.

이때 양의 수가 늑대의 수보다 많다면 양이 싸움에서 이기는 것이고,

양의 수가 늑대의 수보다 작거나 같다면 양이 싸움에서 지는 것으로 구현하면 된다.

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

int r, c, wolf, sheep;
char field[251][251];
bool vis[251][251];

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

void findSheepAndWolf(int x, int y)
{
	int w = 0, s = 0;
	queue<pair<int, int >> q;
	q.push({ x,y });
	vis[x][y] = true;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		if (field[x][y] == 'v') w++;
		if (field[x][y] == 'k') s++;

		for (int i = 0; i < 4; ++i)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
			if (field[nx][ny] != '#' && !vis[nx][ny])
			{
				vis[nx][ny] = true;
				q.push({ nx,ny });
			}
		}
	}

	if (s > w) 
		sheep += s;
	else 
		wolf += w;
}

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

	cin >> r >> c;
	for (int i = 0; i < r; ++i)
		for (int j = 0; j < c; ++j)
			cin >> field[i][j];

	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			if (field[i][j] != '#' && !vis[i][j])
			{
				findSheepAndWolf(i, j);
			}
		}
	}

	cout << sheep << ' ' << wolf << '\n';
	return 0;
}

풀이

N X M 크기의 맵에서 (1,1)에서 출발해서 (N,M)까지 도달하는데 걸리는 최소의 칸 수를 구하는 문제이다.

칸 과 칸 사이는 1이라는 비용으로 생각할 수 있다.

(1,1) -> (1,2) 로 가는 비용이 1이라는 뜻이다. 만약에 비용이 달랐다면 다른 방법으로 풀어야 한다.

비용이 모두 1로 같기 때문에 이 문제는 BFS 알고리즘으로 해결할 수 있다.

여기서는 (0,0) -> (N-1, M-1)로 구현했다.

#include <iostream>
#include <string>
#include <queue>
using namespace std;

int n, m;
int board[101][101];
bool vis[101][101];

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

	queue<pair<pair<int, int>, int> > q;
	q.push({ {0,0}, 1 });
	vis[0][0] = true;
	while (!q.empty())
	{
		int x = q.front().first.first;
		int y = q.front().first.second;
		int cnt = q.front().second;
		q.pop();

		if (x == n - 1 && y == m - 1)
			return cnt;

		for (int i = 0; i < 4; ++i)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			if (board[nx][ny] == 1 && !vis[nx][ny])
			{
				vis[nx][ny] = true;
				q.push({ {nx,ny}, cnt + 1 });
			}
		}
	}

	return -1;
}

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

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		string str;
		cin >> str;
		for (int j = 0; j < str.length(); ++j)
		{
			board[i][j] = str[j] - '0';
		}
	}

	cout << bfs() << '\n';
	return 0;
}

풀이

컴퓨터를 어떻게 코드 상으로 연결할지 생각하자.

이 문제에서는 주어진 간선만 표현하면 되므로 인접 리스트가 편하다.

이때 주의할 점은 양방향 간선으로 그래프를 표현해야 한다.

바이러스의 전파는 무조건 컴퓨터 1번으로부터 시작하므로 1번부터 인접한 컴퓨터를 카운트하면서 진행하면 된다.

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

int v, e;
vector<int> computer[101];
bool vis[101];

int bfs()
{
	int cnt = 0;
	queue<int> q;
	q.push(1);
	vis[1] = true;
	while (!q.empty())
	{
		int now = q.front();
		q.pop();

		for (int i = 0; i < computer[now].size(); ++i)
		{
			int next = computer[now][i];
			if (!vis[next])
			{
				cnt++;
				vis[next] = true;
				q.push(next);
			}
		}
	}

	return cnt;
}

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

	cin >> v >> e;
	for (int i = 0; i < e; ++i)
	{
		int a, b;
		cin >> a >> b;
		computer[a].push_back(b);
		computer[b].push_back(a);
	}

	cout << bfs() << '\n';
	return 0;
}

풀이

약간의 트릭만 잘 찾아내면 쉽게 문제를 해결할 수 있다.

울타리의 최소 개수를 구하는 문제가 아니라, 울타리를 설치해서 양을 늑대로부터 보호에 성공한다면 양은 사는 것이고 아니라면 양은 늑대에게 잡아먹히게 된다.

양이 늑대로부터 살려고 한다면?

가장 간단한 방법은 양의 상, 하, 좌, 우 방향으로 울타리를 설치하면 된다.

그러고 나서 늑대가 맵을 탐색 하면서 양을 찾아내지 못한다면 양은 사는 것이고, 아니라면 잡아먹힌다.

1. 양의 상,하,좌,우 방향으로 울타리를 설치한다. (이때 빈칸인 경우에만 울타리를 설치하자.)

2. 늑대가 양을 찾는다.

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

int r, c;
char board[501][501];
bool vis[501][501];
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };

void print()
{
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			cout << board[i][j];
		}
		cout << '\n';
	}
	cout << '\n';
}

bool findSheep(int x, int y)
{
	queue<pair<int, int >> q;
	q.push({ x,y });
	vis[x][y] = true;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; ++i)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < r && ny < c)
			{
				if (board[nx][ny] == 'S' && !vis[nx][ny]) 
					return true;
				else if (board[nx][ny] != 'D' && !vis[nx][ny])
				{
					vis[nx][ny] = true;
					q.push({ nx,ny });
				}
			}
		}
	}

	return false;
}

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

	cin >> r >> c;
	for (int i = 0; i < r; ++i)
		for (int j = 0; j < c; ++j)
			cin >> board[i][j];

	bool find = false;
	// 양의 4방향으로 울타리를 설치하자.
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			if (board[i][j] == 'S')
			{
				for (int k = 0; k < 4; ++k)
				{
					int nx = i + dx[k];
					int ny = j + dy[k];
					if (nx >= 0 && ny >= 0 && nx < r && ny < c)
					{
						if (board[nx][ny] == '.')
							board[nx][ny] = 'D';
					}
				}
			}
		}
	}

	// 늑대가 양을 찾는다.
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			if (board[i][j] == 'W' && !vis[i][j])
			{
				find = findSheep(i, j);
			}
		}
	}

	if (find)
		cout << 0 << '\n';
	else
	{
		cout << 1 << '\n';
		print();
	}

	return 0;
}

풀이

핵심은 촌수 관계를 어떻게 코드로 풀어낼 것인지다.

이 문제는 N의 범위가 100밖에 되지 않기 때문에 인접 행렬 or 인접 리스트 중 하나를 선택해서 구현하면 된다.

인접 리스트로 구현한다고 할 때,

부모 자식 간의 관계를 나타내는 번호가 a, b로 주어지게 된다면, 서로 양방향으로 넣어줘야 한다는 것만 주의하면 쉽게 해결할 수 있다.

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

// 어떻게 촌수를 표현할 지?
vector<int> v[101];
bool vis[101];
int n, m, x, y;

int bfs()
{
	queue<pair<int, int>> q;
	q.push({ x,0 });
	vis[x] = true;
	while (!q.empty())
	{
		int now = q.front().first;
		int cost = q.front().second;
		q.pop();

		if (now == y) return cost;

		for (int i = 0; i < v[now].size(); ++i)
		{
			int next = v[now][i];
			if (!vis[next])
			{
				vis[next] = true;
				q.push({ next,cost + 1 });
			}
		}
	}

	// 두 사람이 친척 관계가 없다.
	return -1;
}

int main()
{
	cin >> n >> x >> y >> m;
	for (int i = 0; i < m; ++i)
	{
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	cout << bfs() << '\n';
	return 0;
}

풀이

기존 BFS로 탐색하면서 양을 발견하면 양의 수를 올려주고, 늑대를 발견하면 늑대의 수를 올려준다.

탐색이 끝나면 양의 수와 늑대의 수를 비교해서 양이 더 많다면 양이 살아남고, 아니라면 늑대가 살아남는다.

즉, 한 공간 안에서 늑대의 수와 양의 수를 비교해서 살아남는 것만 잘 구현하면 끝나는 문제.

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

// 공간안에서 양이 늑대보다 많으면 양이 이기고, 아니면 늑대가 이긴다.
// 문제에서 원하는 답은 남은 양과 늑대이다.

int r, c;
char field[251][251];
bool vis[251][251];
int sheep, wolf;
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };

void bfs(int x, int y)
{
	int sheep_count = 0, wolf_count = 0;

	if (field[x][y] == 'o') 
		sheep_count++;
	else if (field[x][y] == 'v') 
		wolf_count++;

	queue<pair<int, int>> q;
	q.push({ x,y });
	vis[x][y] = true;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; ++i)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
			if (field[nx][ny] == 'o' && !vis[nx][ny])
			{
				sheep_count++;
				vis[nx][ny] = true;
				q.push({ nx,ny });
			}
			else if (field[nx][ny] == 'v' && !vis[nx][ny])
			{
				wolf_count++;
				vis[nx][ny] = true;
				q.push({ nx,ny });
			}
			else if(field[nx][ny] == '.' && !vis[nx][ny])
			{
				vis[nx][ny] = true;
				q.push({ nx,ny });
			}
		}
	}

	if (sheep_count > wolf_count) 
		sheep += sheep_count;
	else 
		wolf += wolf_count;
}

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

	cin >> r >> c;
	for (int i = 0; i < r; ++i)
		for (int j = 0; j < c; ++j)
			cin >> field[i][j];

	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			if (field[i][j] != '#' && !vis[i][j])
			{
				bfs(i, j);
			}
		}
	}

	cout << sheep << ' ' << wolf << '\n';
	return 0;
}

풀이

기초적인 BFS 알고리즘을 잘한다고 알았던 내가, 이 문제를 보고 한 동안 머리가 아펐다.

기존 BFS 알고리즘 문제들은 대부분 2차원 배열 안에서 해결할 수 있었지만, 이 문제에서는 그 프레임을 벗어나야 해결할 수 있는 문제였다.

원숭이는 기본적으로 상,하,좌,우로 이동할 수 있지만,

이 원숭이는 특별해서 K번의 말의 능력을 사용해서 마치 나이트처럼 움직일 수 있다.

즉, 기존 원숭이처럼 움직이되 어떠한 경우에서는 말의 능력을 이용하면 더 빨리 도착할 수 있다는 것이다.

핵심은 바로 방문 배열을 3차원 배열로 만드는 것이다.

vis[x][y][k] : (x,y)를 k번의 능력을 사용해서 도달했는지 여부를 체크하는 방문 배열이다.

무슨 말이냐면,

(4,5)를 온 경우를 생각해보자.

(4,5)라는 지점을 원숭이가 그냥 능력을 사용하지 않아서 온 경우도 있을 것이다.

이 때는 능력을 사용하지 않았기 때문에 능력의 사용 횟수는 똑같다.

(4,5)라는 지점을 원숭이가 말의 능력을 사용해서 온 경우도 있다는 것이다.

이 때는 능력을 사용했기 때문에 이전에 k번의 능력을 사용해서 왔다면

지금은 (4,5)를 밟기 위해서 k + 1번의 능력을 사용해서 온 경우가 된다.

최단 경로는 누가 더 빨리 와서 그 고지점을 먼저 밟냐 안 밟냐에 따라 승부가 갈리기 때문에

먼저 들어온 녀석이 방문 배열을 true로 만들게 된다.

나머지는 기존 BFS 알고리즘처럼 짜면 풀 수 있게 된다.

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

int mx[] = { 0,0,1,-1 };
int my[] = { 1,-1,0,0 };
int hx[] = { -1,-2,-2,-1,1,2,2,1 };
int hy[] = { -2,-1,1,2,-2,-1,1,2 };

int w, h, k;
int board[201][201];
bool vis[201][201][31]; // vis[x][y][k] : (x,y)지점에 능력을 k번 사용해서 왔습니다.

struct Monkey
{
	int x;
	int y;
	int cost;
	int used;
};

int bfs()
{
	queue<Monkey> q;
	q.push({ 0,0,0,0 });
	vis[0][0][0] = true;
	while (!q.empty())
	{
		Monkey m = q.front();
		q.pop();

		if (m.x == h - 1 && m.y == w - 1) return m.cost;

		// 말의 능력을 사용할 수 있다면
		if (m.used < k)
		{
			for (int i = 0; i < 8; ++i)
			{
				int nx = m.x + hx[i];
				int ny = m.y + hy[i];
				if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
				if (board[nx][ny] == 0 && !vis[nx][ny][m.used + 1])
				{
					vis[nx][ny][m.used + 1] = true;
					q.push({ nx,ny,m.cost + 1, m.used + 1 });
				}
			}
		}

		for (int i = 0; i < 4; ++i)
		{
			int nx = m.x + mx[i];
			int ny = m.y + my[i];
			if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
			if (board[nx][ny] == 0 && !vis[nx][ny][m.used])
			{
				vis[nx][ny][m.used] = true;
				q.push({ nx,ny,m.cost + 1, m.used });
			}
		}
	}

	return -1;
}

int main()
{
	freopen("input.txt", "r", stdin);

	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> k >> w >> h;
	for (int i = 0; i < h; ++i)
	{
		for (int j = 0; j < w; ++j)
		{
			cin >> board[i][j];
		}
	}

	cout << bfs() << '\n';
	return 0;
}