삼성 SW 기출 문제 풀이 모음

 

더보기를 누르면 정답 코드를 볼 수 있습니다. 모두 화이팅입니다.

---

www.acmicpc.net/problem/14502

14502번: 연구소

#include <algorithm>
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <memory.h>
#include <math.h>
#include <map>
#include <queue>
#include <set>
using namespace std;
#define MOD (1000000007LL)
typedef long long ll;
typedef pair<int, int> pii;
int n, m;
int arr[9][9];
int nx[4] = { 0,0,-1,1 };
int ny[4] = { -1,1,0,0 };
vector<pii> v;
int dfs() {
	bool visit[9][9] = { 0, };
	queue<pii> q;
	for (auto p : v) {
		q.push(p);
		visit[p.first][p.second] = 1;
	}
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int _x = x + nx[i];
			int _y = y + ny[i];
			if (_x < 0 || _y < 0 || _x >= n || _y >= m || visit[_x][_y] || arr[_x][_y]) {
				continue;
			}
			visit[_x][_y] = 1;
			q.push({_x, _y});
		}
	}
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!visit[i][j] && !arr[i][j]) {
				cnt += 1;
			}
		}
	}
	return cnt;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 2) {
				v.push_back({ i,j });
			}
		}
	}
	int answer = 0;
	for (int a = 0; a < n * m; a++) {
		int x1 = a / m;
		int y1 = a % m;
		if (arr[x1][y1] == 0) {
			arr[x1][y1] = 1;
			for (int b = a + 1; b < n * m; b++) {
				int x2 = b / m;
				int y2 = b % m;
				if (arr[x2][y2] == 0) {
					arr[x2][y2] = 1;
					for (int c = b + 1; c < n * m; c++) {
						int x3 = c / m;
						int y3 = c % m;
						if (arr[x3][y3] == 0) {
							arr[x3][y3] = 1;
							// to do something
							answer = max(answer,dfs());
							//
							arr[x3][y3] = 0;
						}
					}
					arr[x2][y2] = 0;
				}
			}
			arr[x1][y1] = 0;
		}
	}
	cout << answer;
}

 

---

www.acmicpc.net/problem/14890

14890번: 경사로

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <string>

using namespace std;
int n, l;
int buf[101][101];
bool open[101][101][4] = { 0, };
int nx[4] = { -1,0,1,0 };
int ny[4] = { 0,1,0,-1 };


bool DFS(int sx, int sy, int k) {
	// 진행하면서 경사로를 둘 수 없거나
	// 끝까지 진행 못하는 경우 false

	// true;

	// 가다가 현재 좌표에서 k 방향으로 경사로를 둘 수 있다면 
	// 한번에 그 끝지점으로 이동하는게 한칸한칸 이동하는거보다 빠름
	// open[x][y][k] == 0 // k방향으로 한칸 
	// 1 인 경우 // (x,y)에서 (x+nx[k]*l, y +ny[k]*l) 갈 수 있다.
	int cur_x = sx;
	int cur_y = sy;
	bool flag = true;
	int pre = 0; 
	if (k == 1) {
		// cur_y == n-1 일때까지 진행
		while (cur_y < n - 1) { 
			if (open[cur_x][cur_y][k] == 1) {// 경사로가 있는경우
				int tmp_y = cur_y;
				cur_y = cur_y + ny[k] * l;
				int _f = (buf[cur_x][tmp_y] < buf[cur_x][cur_y] ? 1 :-1);
				if (pre != -1 || pre == _f ) { // 이전에 경사로를 쓰지 않았거나 연속된 기울기로 진행하면
					pre = _f; // 이전에 사용한 경사로를 _f 로 
					continue;
				}
				cur_y = tmp_y;
			}
			pre = 0;
			// 경사로가 없는경우, 이전에 경사로를 둔 경우
			// 다음 칸이랑 높이가 다를수도있음
			if (buf[cur_x][cur_y] != buf[cur_x + nx[k]][cur_y + ny[k]]) {
				flag = false;
				break;
			}
			else {
				cur_y = cur_y + ny[k];
			}
		}
	}
	else { // k == 2 일때
		// cur_x == n-1 일때까지 진행
		while (cur_x < n - 1) {
			if (open[cur_x][cur_y][k] == 1) {// 경사로가 있는경우
				int tmp_x = cur_x;
				cur_x = cur_x + nx[k] * l;
				int _f = (buf[tmp_x][cur_y] < buf[cur_x][cur_y] ? 1 : -1);
				if (pre != -1 || pre == _f) { // 이전에 경사로를 쓰지 않았거나 연속된 기울기로 진행하면
					pre = _f;  // 이전에 사용한 경사로를 _f 로 
					continue;
				}
				cur_x = tmp_x;
			}
			pre = 0;
			// 경사로가 없는경우, 이전에 경사로를 둔 경우
			// 다음 칸이랑 높이가 다를수도있음
			if (buf[cur_x][cur_y] != buf[cur_x + nx[k]][cur_y + ny[k]]) {
				flag = false;
				break;
			}
			else {
				cur_x = cur_x + nx[k];
			}
			
		}
	}

	return flag;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> l;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> buf[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < 4; k++) {
				int flag = 1;
				int _x, _y;
				for (int o = 1; o <= l; o++) {
					_x = i + nx[k] * o;
					_y = j + ny[k] * o;
					if (_x < 0 || _y < 0 || _x >= n || _y >= n) {
						flag = 0;
					}
					if (buf[_x][_y] + 1 != buf[i][j]) {
						flag = 0;
					}
				}
				if (flag) {
					open[i][j][k] = 1;  // i,j를 기점으로 k방향으로 경사로를 둘 수 있다
					open[_x][_y][(k + 2) % 4] = 1;
					// x,y 에서 k방향으로 경사로를 둘 수 있다
					// (x,y)에서 (x+nx[k]*l, y +ny[k]*l) 갈 수 있다.
				}

			}
		}
	}

	//     (x,y) x = 0 우리는 아래방향으로만 진행
	//		y =0 오른쪽 방향으로만 진행
	// 
	int answer = 0;
	for (int i = 0; i < n; i++) { // x가 0 아래방향으로
		bool res = DFS(0, i, 2);
		//cout << res << " : " << " (0," << i << ")\n";
		answer += res;
	}
	for (int i = 0; i < n; i++) { // y 가 0
		bool res = DFS(i, 0, 1);
		//cout << res << " : " << " (" << i << ", 0)\n";
		answer += res;
	}
	cout << answer;

}

 

---

www.acmicpc.net/problem/15686

15686번: 치킨 배달

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <queue>
#include <map>
#include <vector>
#include <string>
#define MOD (1234567891LL)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n, m, arr[51][51];
int dist[51][51][51][51];
vector<pii> a, b;
int tmp[51] = { 0, }; // i번째 치킨집 폐업
int ans = 1e9;
void recv(int idx, int level) {
	if (!level) {
		int cnt = 0;
		for (auto h : a) {
			int _min = 1e9;
			for (int i = 0; i < b.size(); i++) {
				if (tmp[i]) {
					_min = min(_min, dist[h.first][h.second][b[i].first][b[i].second]);
				}
			}
			cnt += _min;
		}
		ans = min(ans, cnt);
		return;
	}
	if (idx == b.size()) {
		return;
	}
	for (int i = idx; i < b.size(); i++) {
		tmp[i] = 1;
		recv(i + 1, level - 1);
		tmp[i] = 0;
	}
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	memset(dist, -1, sizeof(dist));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 1) {
				a.emplace_back(i, j);
			}
			if (arr[i][j] == 2) {
				b.emplace_back(i, j);
			}
		}
	}
	for (auto h : a) {
		for (auto c : b) {
			dist[h.first][h.second][c.first][c.second] = abs(h.first - c.first) + abs(h.second - c.second);
		}
	}
	recv(0, m);
	cout << ans;
}

 

---

www.acmicpc.net/problem/16234

16234번: 인구 이동

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;

bool open[51][51][4]; // open[i][j][0] = 1 // 위 쪽으로 오픈 
int map[51][51];
int _move[2501];
int visit[51][51];
int mx[4] = { -1,0,1,0 }; // 위 , 오른 , 아래, 왼쪽
int my[4] = { 0,1,0, -1 };


int n, l, r; // 국경선개방 조건 두나라인구차이 L명이상 R명 이하

pair<int,int> BFS(int a, int b,int id) {
	
	queue<pair<int, int> > q;
	visit[a][b] = id;
	q.push(make_pair(a, b));

	int sum = 0;
	int num = 0;

	while (!q.empty()) { // 내가 방문할 나라의 좌표가 pop
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		sum += map[x][y];
		num += 1;


		for (int i = 0; i < 4; i++) { // 상, 우, 하, 좌
			int nx = x + mx[i];
			int ny = y + my[i];
			if (nx<0 || ny<0 || nx>n - 1 || ny>n - 1) continue;
			if (open[x][y][i] && visit[nx][ny] == 0) { // 네 방향에 대해서 국경이 열렸다.
				visit[nx][ny] = id;
				q.push({ nx,ny });
			}
		}
	}
	
	// 모든 연합 국가 탐색이 완료
	return make_pair(sum, num);
}

int main() {

	cin >> n >>  l >>  r;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	int step =0;
	while (1) {
		memset(open, 0, sizeof(open)); // 국경 오픈 여부  // 전부 닫힘

		int flag = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 1; k < 3; k++) {
					int adj_i = i + mx[k];
					int adj_j = j + my[k];
					if (adj_i >= n || adj_j >= n) {
						continue;
					}

					int dif = abs(map[i][j] - map[adj_i][adj_j]);
					if (dif >= l && dif <= r) {

						flag = 1;

						open[i][j][k] = 1;
						open[adj_i][adj_j][(k+2)%4] = 1;
					}
				}
			}
		}

		memset(visit, 0, sizeof(visit));
		int id = 1; // 
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (visit[i][j] == 0) { // 
					// BFS, DFS

					// visit[i][j] = id;
					pair<int,int> res = BFS(i,j,id);  // {sum, num}
					// 
					int after = res.first / res.second;
					_move[id] = after;
					id++;
				}
				
			}
		}

		if (flag == 0) { // 인구이동이 일어나지않은 조건
			break;
		}
		// 인구 이동이 일어남
		step += 1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (visit[i][j] != 0) { // 인구 이동이 일어난 경우
					map[i][j] = _move[visit[i][j]];
				}
			}
		}

	/*	for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cout << map[i][j] << " ";
			}
			cout << "\n";
		}
		cout << "인구 이동 끝 \n";*/
	}

	cout << step;
	return 0;
}

 

---

www.acmicpc.net/problem/16236

16236번: 아기 상어

#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <string>
#define MOD (1234567891LL)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n;
int arr[21][21];
vector<pii> v[10];
bool visit[21][21] = { 0, };

int nx[4] = { 0,0,1,-1 };
int ny[4] = { -1,1,0,0 };
pair<int,pii> find_fish(int x, int y, int _size) {
	bool check[21][21] = { 0, };
	check[x][y] = 1;
	queue<pair<int,pii> > q;
	q.push({ 0, { x, y } });
	vector<pii> list[401];
	int flag = 0;
	while (!q.empty()) {
		int T = q.front().first;
		int X = q.front().second.first;
		int Y = q.front().second.second;
		q.pop();
		if (arr[X][Y] < _size && arr[X][Y]) {
			flag = 1;
			list[T].emplace_back(X, Y);
		}
		for (int i = 0; i < 4; i++) {
			int _X = X + nx[i];
			int _Y = Y + ny[i];
			if (_X < 0 || _Y <0 || _X >= n || _Y >= n || arr[_X][_Y] > _size || check[_X][_Y]) {
				continue;
			}
			check[_X][_Y] = 1;
			q.push({ T + 1, { _X, _Y } });
		}
	}
	if (!flag) {
		return { -1, {-1,-1} };
	}
	else {
		for (int i = 0; i < 401; i++) {
			if (list[i].size()) {
				sort(list[i].begin(), list[i].end());
				return { i,list[i][0] };
				break;
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	int idx = 0;
	int sx,sy;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 9) {
				sx = i, sy = j;
			}
		}
	}
	int cur = 0;
	int _size = 2;
	int ans = 0;
	arr[sx][sy] = 0;
	while (1) {
		pair<int,pii> a = find_fish(sx, sy, _size);
		if (~a.first) {
			int d =a.first;
			ans += d;
			sx = a.second.first;
			sy = a.second.second;
			arr[sx][sy] = 0;
			cur += 1;
			if (cur == _size) {
				cur = 0;
				_size += 1;
			}
		}
		else {
			break;
		}
	}
	cout << ans;
}

 

---

www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

#include <algorithm>
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <memory.h>
#include <math.h>
#include <map>
#include <queue>
#include <set>
using namespace std;
#define MOD (1000000007LL)
typedef long long ll;

int after[51][51] = { 0, };
int before[51][51] = { 0, };
int n, m, t;
int air_y;
int nx[4] = { 0,0,-1,1 };
int ny[4] = { -1,1,0,0 };

void spread(int x, int y) {
	int sp = before[x][y] / 5;
	int cnt = 0;
	for (int i = 0; i < 4; i++) {
		int _x = x + nx[i];
		int _y = y + ny[i];
		if (_x < 0 || _y < 0 || _x >= n || _y >= m || (_y == 0 && (_x == air_y || _x == air_y+1))) {
			continue;
		}
		cnt += 1;
		after[_x][_y] += sp;
	}
	after[x][y] += (before[x][y] - cnt * sp);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> t;
	air_y = -1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> before[i][j];
			if (before[i][j] == -1) {
				if (air_y == -1) {
					air_y = i;
				}
			}
		}
	}
	while (t--) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (before[i][j] >= 0) {
					spread(i, j);
				}
				else {
					after[i][j] = -1;
				}
			}
		}

		for (int i = air_y - 1; i > 0; i--) {
			after[i][0] = after[i - 1][0];
		}
		for (int i = 0; i < m-1; i++) {
			after[0][i] = after[0][i + 1];
		}
		for (int i = 0; i < air_y; i++) {
			after[i][m - 1] = after[i + 1][m - 1];
		}
		for (int i = m-1; i > 1; i--) {
			after[air_y][i] = after[air_y][i - 1];
		}
		after[air_y][1] = 0;

		for (int i = air_y + 2; i < n-1; i++) {
			after[i][0] = after[i + 1][0];
		}
		for (int i = 0; i < m - 1; i++) {
			after[n - 1][i] = after[n - 1][i + 1];
		}
		for (int i = n - 1; i > air_y +1; i--) {
			after[i][m - 1] = after[i - 1][m - 1];
		}
		for (int i = m - 1; i > 1; i--) {
			after[air_y + 1][i] = after[air_y + 1][i - 1];
		}
		after[air_y+1][1] = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				before[i][j] = after[i][j];
				after[i][j] = 0;
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			ans += before[i][j];
		}
	}
	cout << ans + 2;
}

 

---

www.acmicpc.net/problem/14500

14500번: 테트로미노

#include <iostream>
#include <algorithm>
#include <queue>
#include <memory.h>
#include <map>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n, m, arr[501][501];
int ans = 0;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}
	int filter[19][2][4] = {
		{{0,0,1,1},{0,1,0,1}},

		{{0,0,0,0},{0,1,2,3}},
		{{0,1,2,3},{0,0,0,0}},

		{{0,1,2,2},{0,0,0,1}},
		{{0,1,2,2},{0,0,0,-1}},
		{{0,0,1,2},{0,-1,-1,-1}},
		{{0,0,1,2},{0,1,1,1}},

		{{0,-1,-1,-1},{0,0,1,2}},
		{{0,-1,-1,-1},{0,0,-1,-2}},
		{{0,1,1,1},{0,0,1,2}},
		{{0,1,1,1},{0,0,-1,-2}},

		{{0,1,1,2},{0,0,1,1}},
		{{0,1,1,2},{0,0,-1,-1}},
		{{0,0,1,1},{0,1,1,2}},
		{{0,0,-1,-1},{0,1,1,2}},


		{{0,0,0,1},{0,1,2,1}},
		{{0,0,0,-1},{0,1,2,1}},
		{{0,1,2,1},{0,0,0,1}},
		{{0,1,2,1},{0,0,0,-1}}
	};
	for (int i = 0; i < 19; i++) {
		for (int x = 0; x < n; x++) {
			for (int y = 0; y < m; y++) {
				int cnt = 0;
				int flag = 1;
				for (int k = 0; k < 4; k++) {
					int _x = x + filter[i][0][k];
					int _y = y + filter[i][1][k];
					if (_x < 0 || _y < 0 || _x >= n || _y >= m) {
						flag = 0;
						break;
					}
					cnt += arr[_x][_y];
				}
				if (flag) {
					ans = max(ans, cnt);
				}
			}
		}
	}
	cout << ans;
	return 0;
}