알고리즘 문제 추천 및 해설(1)
삼성 SW 역량 테스트 기출 문제 중 하나이다.
BOJ 16234번: 인구이동
문제풀이
인구가 이동할 수 있을 때까지 계속해서 인구이동을 해줘야 겠구나라고 먼저 생각이 들어야한다. 이 부분을 체크하기 위해 flag를 사용한다. 나라를 방문체크 하기위한 배열 check배열을 사용한다. 기존의 bfs를 구현하면 Queue를 사용할 것이다. 이 큐에는 시작지점에서 부터 방문을 할 수 있는 구역들을 탐색하며 큐에 담는 역할을 하는데, 이 문제에서는 이런 역할을 하는 큐하나와 문제의 조건에서 국경선을 공유하는 두 나라의 diff가 L이상 R이하인 부분의 조건이 성립하는 좌표를 저장할 수 있는 큐가 한개 더 필요로하다.
정리
1. 방문을 하지 않았다면 bfs를 돌린다.
2. 조건에 맞는 나라들만 탐색하여 조건에 맞는 나라들이 있을 경우 기존 나라의 배열의 값을 수정해준다.
3. 더 이상 조건에 부합하는 나라가 없다면 종료하고 결과를 출력한다.
코드
#include <bits/stdc++.h>
using namespace std;
int n, l, r;
int arr[51][51];
bool check[51][51];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
int ret;
bool flag;
void bfs(int y, int x) {
queue<pair<int, int>> q, qu;
q.push({ y,x });
qu.push({ y,x });
check[y][x] = true;
int sum = 0;
int cnt = 0;
while (!qu.empty()) {
int oy = qu.front().first;
int ox = qu.front().second;
qu.pop();
sum += arr[oy][ox];
cnt += 1;
for (int i = 0; i < 4; i++) {
int ny = dy[i] + oy;
int nx = dx[i] + ox;
int diff = abs(arr[ny][nx] - arr[oy][ox]);
if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
if (diff >= l && diff <= r && !check[ny][nx]) {
check[ny][nx] = true;
q.push({ ny,nx });
qu.push({ ny,nx });
flag = true;
}
}
}
int newPeople = sum / cnt;
if (flag) {
while (!q.empty()) {
int my = q.front().first;
int mx = q.front().second;
q.pop();
arr[my][mx] = newPeople;
}
}
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
cin >> n >> l >> r;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
}
}
while (true) {
flag = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!check[i][j]) {
bfs(i, j);
}
}
}
if (flag) {
memset(check, false, sizeof(check));
ret++;
}
else break;
}
cout << ret;
}
회고
삼성의 문제는 조금 더 심화된 구현을 요구하는 것 같다. 간단하게 bfs를 생각하였지만 생각보다 조금 더 생각해야 문제를 해결할 수 있었다. 삼성 SW 기출 문제들을 좀 풀어보면서 빡구현의 문제들의 감을 잡아야겠다.
이 문제는 지훈이가 먼저 이동하고 불을 이동시킨 후 제출하게 되면 틀렸다고 나오게된다. 불을 먼저 이동시켜야 성공하게 되는데, 정확한 조건이 없으니 애매한 문제인 것 같다.
문제풀이
단순하게 생각해보면 bfs를 두 번 돌려서 문제를 풀어 볼 수 있다. 먼저 무식하게 지훈이와 불을 따로 bfs를 돌려서 지훈이가 불을 피해서 갈 수 있는지 생각해보면 불이 번지는 시간을 계산한다음 지훈이가 각각의 영역에 도달하는 부분이 불이 도달하는 시간보다 작다면 지훈이는 안전하게 그 영역을 통과할 수 있을 것이다.
d1은 지훈이가 이동하는 체크배열이라 볼 수 있고, d는 불이 이동하는 체크배열이라 생각하면 된다. d1[oy][ox] + 1 >= d[ny][nx] && d[ny][nx] 이 조건은 지훈이가 새로운 영역을 가려고할 때, 지훈이가 이동한 시간이 불이 번지는 시간보다 도착 시간이 더 오래 걸리면 지훈이는 타죽기 때문에 갈 수 없다.
코드
#include <bits/stdc++.h>
using namespace std;
int r, c;
string arr[1001];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
int d[1001][1001];
int d1[1001][1001];
queue<pair<int, int>> q, qu;
int bfs() {
while (!q.empty()) {
int oy = q.front().first;
int ox = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int ny = oy + dy[i];
int nx = ox + dx[i];
if (ny < 0 || ny >= r || nx < 0 || nx >= c) {
return d1[oy][ox];
}
if (arr[ny][nx] == '#' || d1[ny][nx]) continue;
if (d1[oy][ox] + 1 >= d[ny][nx] && d[ny][nx]) continue;
d1[ny][nx] = d1[oy][ox] + 1;
q.push({ ny,nx });
}
}
return -1;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
cin >> r >> c;
for (int i = 0; i < r; i++) {
cin >> arr[i];
for (int j = 0; j < c; j++) {
if (arr[i][j] == 'J') {
d1[i][j] = 1;
q.push({ i,j });
}
if (arr[i][j] == 'F') {
d[i][j] = 1;
qu.push({ i,j });
}
}
}
while (!qu.empty()) {
int oy = qu.front().first;
int ox = qu.front().second;
qu.pop();
for (int i = 0; i < 4; i++) {
int ny = oy + dy[i];
int nx = ox + dx[i];
if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
if (d[ny][nx] || arr[ny][nx] == '#') continue;
d[ny][nx] = d[oy][ox] + 1;
qu.push({ ny,nx });
}
}
int ret = bfs();
if (ret == -1) cout << "IMPOSSIBLE";
else cout << ret;
}
회고
변수명 작성에 유의하면서 코드를 작성하고 bfs를 사용할 때는 안되는 조건문을 먼저 작성하여 continue 시켜주는 습관을 가지도록 하겠다.
뮤탈리스크는 3쿠션으로 대상을 공격할 수 있습니다.
문제풀이
1~3마리의 SCV를 공격한다고 한다. 즉 한번의 공격에 첫번째 쿠션은 -9 두번째 쿠션은 -3 세번째 쿠션은 -1의 데미지를 주게된다.
어떤 대상을 공격하느냐에 따라서 공격을 줄 수 있는 데미지가 각각 다르다. {-9,-3,-1}, {-9,-1,-3}, {-1,-9,-3}, {-1,-3,-9}, {-3,-1,-9}, {-3,-9,-1}의 6가지 경우의 수가 나올 수 있다. 이 문제는 최소의 경우의 수를 구해야하고 우리가 좌표로 따졌을 때 움직일 수 있는 말의 좌표가 일정하다. 그렇다면 bfs로 해결할 수 있다. scv 체력이 (0,0,0)이 되었을 때 bfs로 탐색하였을 때 최소의 최단거리를 구할 수 있다.
코드
#include <bits/stdc++.h>
using namespace std;
int n;
int check[61][61][61];
int arr[4];
int ret;
int attack[6][3] = {
{9,3,1},{9,1,3},{3,9,1},{3,1,9},{1,3,9},{1,9,3}
};
struct scv {
int a, b, c;
};
queue<scv> qu;
void bfs(int a,int b,int c) {
check[a][b][c] = 0;
qu.push({ a,b,c });
while (!qu.empty()) {
int ox = qu.front().a;
int oy = qu.front().b;
int oz = qu.front().c;
qu.pop();
if (ox == 0 && oy == 0 && oz == 0) {
ret = check[ox][oy][oz];
return;
}
for (int i = 0; i < 6; i++) {
int nx = max(0,ox - attack[i][0]);
int ny = max(0,oy - attack[i][1]);
int nz = max(0,oz - attack[i][2]);
if (check[nx][ny][nz] != -1) continue;
check[nx][ny][nz] = check[ox][oy][oz] + 1;
qu.push({ nx,ny,nz });
}
}
return;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
memset(check, -1, sizeof(check));
bfs(arr[0], arr[1], arr[2]);
cout << ret;
}
회고
가중치가 일정하고 움직일 수 있는 조건이 정해져있다면 bfs를 생각하여 최소의 경로를 찾아보자. 이 문제의 경우 다이나믹프로그래밍으로 풀 수 있다. 하지만 위의 형태를 자세히 보면 메모이제이션 하면서 모든 영토를 확인하는 것으로 bfs는 언제나 최소의 결과 값을 저장하니 요런식으로도 풀 수 있다.
문제풀이
이 문제는 언뜻보면 bfs나 dfs로 최소의 거리를 구하면 될 것 같아보이지만, 모든 경로의 거리 수를 구해야 하는 문제입니다. 그렇다면 dfs를 이용하여 끝까지 한 가지 경로로 깊숙히 목적지 까지 들어가면서 만약 지금 상태에서 방문이 완료되었다면 check배열을 초기화 시켜주고 다시 새로운 경로를 방문할 수 있게 해줘야한다.
코드
#include <bits/stdc++.h>
using namespace std;
int r, c, k;
char arr[6][6];
int check[6][6];
int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };
int ret;
void go(int y, int x) {
if (y == 0 && x == c - 1) {
if (check[y][x] == k) {
ret++;
}
return;
}
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
if (check[ny][nx] != 0||arr[ny][nx]=='T') continue;
check[ny][nx] = check[y][x] + 1;
go(ny, nx);
check[ny][nx] = 0;
}
return;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
cin >> r >> c >> k;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> arr[i][j];
}
}
check[r-1][0] = 1;
go(r-1, 0);
cout << ret;
}
회고
일명 dfs와 bfs형식을 반반 섞은 느낌으로도 문제를 풀 수 있다. 이 경우 모든 경로를 탐색하기 위해 사용하므로 잘 숙지해둬야 겠다.
문제풀이
key point
- 큰 색종이부터 붙이기.
- 전체 경우를 탐색해보면서 기저사례를 생각해서 백트래킹으로 구현하기.
재귀를 활용한 그리디 문제라고 볼 수 있다. 그리디 한 생각은 큰 색종이 부터 먼저 붙인다는 점이다. 이후에 (0,0)에서부터 (max,max)까지 x축을 한칸 씩 옮기면서 전체를 탐색하는 방법을 선택한다.
기저사례 생각해본다면, 먼저 정답은 최소 값만을 가지고 있으면 된다. 하지만 현재 가지고 있는 최소 값이 이미 나왔는데, 색종이를 현재 붙인 개수가 더 많거나 같으면 탐색할 가치가 없기 때문에 바로 리턴해준다. (0,0)에서 부터 차례대로 x축을 기준으로 한 칸씩 오른족으로 땡기면서 탐색을 하는데 어떻게 범위를 벗어나게 되었는지 판단하기 위해 x==10이 되었다면 한 행의 오른쪽을 다 탐색 했다는 뜻이므로 행을 하나 내려서 탐색해줘야 한다. 마찬가지로 y==10이 된 경우는 전체 맵을 다 탐색했다는 뜻으로 정답을 비교해주면 된다. 마지막 기저사례로는 맵이 색종이를 붙일 수 없는 공간이면 당연히 리턴해준다.
이 문제는 BOJ 1189번과 비슷한 방식의 dfs를 사용한다. 이 문제의 주요포인트는 최소의 경로를 탐색하는게 아니라 전체 탐색할 수 있는 방법의 개수를 필요로 한 문제이다. 마찬가지로 색종이 붙이기 문제도 전체를 탐색해야 하지만, 색종이의 경우의 수를 전체를 고려해야 하기 때문에 5x5~1x1의 색종이를 차례로 비교하기 위해서 맵에 색종이를 붙였다가 다시 떼어 내는 방법이 이 문제와 유사하다. 즉 1189번 문제도 전체의 경우를 탐색하기 위해서 맵에 기록을 하면서 이동하고 답을 도출하였으면 새로운 길을 도출하기 위해서 맵의 기록을 지운다.
소스코드
#include <bits/stdc++.h>
using namespace std;
int arr[11][11];
int ret = 987654321;
int color[6];
queue<pair<int, int>> qu;
bool check[11][11];
bool isMake(int y, int x, int size) {
int ny = y + size;
int nx = x + size;
if (ny < 0 || ny > 10 || nx < 0 || nx > 10) return false;
for (int i = y; i < y + size; i++) {
for (int j = x; j < x + size; j++) {
if (arr[i][j] != 1) {
return false;
}
}
}
return true;
}
void draw(int y, int x, int size, int c) {
for (int i = y; i < y + size; i++) {
for (int j = x; j < x + size; j++) {
arr[i][j] = c;
}
}
}
void dfs(int y, int x, int cnt) {
if (cnt >= ret) return;
if (x == 10) {
dfs(y + 1, 0, cnt);
return;
}
if (y == 10) {
ret = min(cnt, ret);
return;
}
if (arr[y][x] == 0) {
dfs(y, x + 1, cnt);
return;
}
for (int len = 5; len > 0; len--) {
if (color[len] == 5) continue;
if (isMake(y, x, len)) {
color[len]++;
draw(y, x, len, 0);
dfs(y, x + len, cnt + 1);
draw(y, x, len, 1);
color[len]--;
}
}
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
int onecnt = 0;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
cin >> arr[i][j];
if (arr[i][j] == 1) {
onecnt++;
}
}
}
if (onecnt == 0) cout << 0;
else {
dfs(0, 0, 0);
if (ret == 987654321) {
cout << -1;
}
else cout << ret;
}
}
회고
재귀를 활용하여 백트래킹하는 문제들을 좀 더 풀어보면서 감을 익혀야하겠다. 삼성 SW 기출문제들을 주로 풀어보면서 대부분의 문제들이 브루트포스를 이용한 구현 문제가 많이 출제되므로 기출 문제들을 위주로 좀 풀어보도록 하겠다.
문제풀이
결국 이 문제는 앞에서부터 처리하는 문제지만, 우선순위인 괄호를 추가하게 된다면 그 결과부터 계산하고 다시 앞에서부터 계산하는 형태의 문제이다.
DAG는 Directed Acyclic Graph 이다. 방향이 존재하고 사이클이 없는 그래프를 의미한다. 수식의 길이를 가지고 앞에서 부터 괄호를 붙이는 가 안붙이는 가에 따라 순서가 결정된다. 즉 뒤로는 갈일이 없고 앞으로만 쭉쭉 이어지는 그래프를 만들 수 있다.
input
5
1*2+1
이런 형태의 입력이 들어왔다고 생각해보자. (1*2)+1의 경우와 1*(2+1)의 경우로 2가지 경우가 있고, index를 가지고 관리를 해주면 편리하게 문제를 해결할 수 있다. 먼저 정수, 연산자 vector를 선언하여 넣어주자.
그럼 현재 vector에는 정수 - 1 2 1 연산자 - * + 이런 형태로 vector에 들어가있겠죠? 첫번째 경우의 수를 계산하기 위한 식을 생각해보자. 0번째 인덱스의 * 연산을 사용해야하고, 정수의 1 2를 사용해야한다. 이는 코드를 직접보면 빠르게 이해될 것이다.
go(index + 1, oper(op[index], sum, num[index + 1]));
이렇게하면 앞에 두 숫자를 먼저 연산하는 식이 완성된다. 뒤에 있는 연산자 먼저 계산해야하는 경우에는 배열 인덱스 초과예외를 생각해주고 (2+1)을 먼저 계산해줘야 하므로 먼저 계산을 해준다. 이는 바로 여기서 확인할 수 있다.
int temp = oper(op[index + 1], num[index + 1], num[index + 2]);
이후에 먼저 계산한 결과와 앞에서 대기하고 있는 수와 계산해주면 됩니다.
go(index + 2, oper(op[index], sum, temp));
코드
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int ret = -987654321;
vector<int> num;
vector<char> op;
int oper(char o, int a, int b) {
if (o == '+') return a + b;
if (o == '-') return a - b;
if (o == '*') return a * b;
}
void go(int index,int sum) {
if (index >= num.size()-1) {
ret = max(ret, sum);
return;
}
go(index + 1, oper(op[index], sum, num[index + 1]));
if (index + 2 <= num.size() - 1) {
int temp = oper(op[index + 1], num[index + 1], num[index + 2]);
go(index + 2, oper(op[index], sum, temp));
}
return;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
cin >> n >> s;
for (int i = 0; i < n; i++) {
if ('0' <= s[i] && s[i] <= '9') {
num.push_back(s[i] - '0');
}
else op.push_back(s[i]);
}
go(0, num[0]);
cout << ret;
}
회고
생각보다 문제를 어렵게 생각해서 쉽게 풀리지 않은 문제였다. 하지만 문제를 제대로 이해해보니 오른쪽 방향으로만 가지치기 해서 그래프를 만들어보니 이해가 쉽게 되 었다. 결국 모든 경우를 다 해보는 것이지만 중첩된 괄호를 사용하는 것도아니고 2가지의 경우 괄호를 쓰는가 안쓰는가 차이로 결과값들이 나눠지게 되므로 단순한 예시를 가지고 재귀문을 작성해보는게 도움이 많이 되었던 것 같다. 이런 문제는 index를 활용하여 문제를 해결하면 정말 쉽게 접근이 가능하니 앞으로 유의해서 생각해봐야 겠다.
문제풀이
이전의 포스팅에서도 좌표상으로 나타냈을 때, 가중치가 같고 움직이는 방법이 정해져 있다면 bfs를 생각해야 한다고 하였다. 이 문제도 마찬가지로 bfs를 구현하면 간단하게 해결할 수 있다.
다만 문제의 범위를 어디까지 하느냐에 따라 문제의 성공여부가 갈리게 되지않을까 싶다. 절대로 이런 경우는 없겠지만, 수빈이의 위치가 100,000이고*2의 순간이동을 하였을 경우 200,000의 좌표가 찍히게 되므로 좌표의 MAX를 200,000으로 잡아두었다. 아마 문제푸는데는 100,000으로 잡아도 지장이 없을거라 생각하지만 안전하게 그냥 200,000으로 박아버렸다.
코드
#include <bits/stdc++.h>
using namespace std;
int n, k;
int check[200001];
queue<int> qu;
int cal(int start,int oper) {
if (oper == 0) {
return start + 1;
}
else if (oper == 1) {
return start - 1;
}
else return start * 2;
}
void go(int start) {
qu.push(start);
check[start] = 0;
while (!qu.empty()) {
int os = qu.front();
qu.pop();
if (os == k) {
return;
}
for (int i = 0; i < 3; i++) {
int ns = cal(os, i);
if (ns < 0 || ns>200000) continue;
if (check[ns] != -1) continue;
check[ns] = check[os] + 1;
qu.push(ns);
}
}
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
cin >> n >> k;
memset(check, -1, sizeof(check));
go(n);
cout << check[k];
}
회고
숨바꼭질2도 풀예정이다.
문제풀이
숨바꼭질 문제풀이 이 문제와 비슷한 로직의 문제이다. 여기서 추가로 찾아야 하는 점은 경우의 수를 찾는게 추가되었다. 경우의 수는 이전의 좌표와 현재의 좌표를 계속해서 +=해주면 된다.
만약 방문하여서 초기 값-1이 아닌 경우인데 최적의 경로인 경우 그대로 가져와야하는 코드만 주의한다면 별로 어려운 점이 없을 것이다.
코드
#include <bits/stdc++.h>
using namespace std;
int n, k;
int check[200001];
int ans[200001];
queue<int> qu;
int cal(int start,int oper) {
if (oper == 0) {
return start + 1;
}
else if (oper == 1) {
return start - 1;
}
else return start * 2;
}
void go(int start) {
qu.push(start);
check[start] = 0;
ans[start] = 1;
while (!qu.empty()) {
int os = qu.front();
qu.pop();
if (os == k) {
return;
}
for (int i = 0; i < 3; i++) {
int ns = cal(os, i);
if (ns < 0 || ns>200000) continue;
if (check[ns] == check[os] + 1) ans[ns] += ans[os];
if (check[ns] != -1) continue;
check[ns] = check[os] + 1;
ans[ns] += ans[os];
qu.push(ns);
}
}
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
cin >> n >> k;
memset(check, -1, sizeof(check));
go(n);
cout << check[k] << "\n" << ans[k];
}
회고
경우의 수를 계산하는 방법을 계속해서 ans[ns]++을 하고 있었다. 경우의 수는 직접 그래프를 그려보면서 다른 경로가 나오기 전까지는 다 같은 방법으로 만들 수 있다는 점을 명심해야겠다.
문제풀이
숨바꼭질 문제풀이 의 응용문제이다. 숨바꼭질4 문제는 최적의 경로를 추적하는 기법이 필요하다. parent[next]=node 배열을 하나 생성하여 현재 노드와 그 다음 노드(방문할 노드)를 저장시켜 주는 것이다. 즉 현재 노드가 부모노드가 되는 것으로 부모노드가 없을 때 까지 탐색하게 되면 이가 바로 최적의 경로의 방문순서라고 볼 수 있다. 이러한 기법을 trace라고 하며 구글 검색에서 bfs 경로 추적이라고 검색하면 좀 더 상세한 내용들을 볼 수 있습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int n, k;
int check[200001];
int parent[200001];
vector<int> v;
queue<int> qu;
int cal(int start,int oper) {
if (oper == 0) {
return start + 1;
}
else if (oper == 1) {
return start - 1;
}
else return start * 2;
}
void go(int start) {
qu.push(start);
check[start] = 0;
while (!qu.empty()) {
int os = qu.front();
qu.pop();
if (os == k) {
return;
}
for (int i = 0; i < 3; i++) {
int ns = cal(os, i);
if (ns < 0 || ns>200000) continue;
if (check[ns] != -1) continue;
check[ns] = check[os] + 1;
parent[ns] = os;
qu.push(ns);
}
}
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
cin >> n >> k;
memset(check, -1, sizeof(check));
go(n);
cout << check[k] << "\n";
for (int i = k; i != n; i = parent[i]) {
v.push_back(i);
}
v.push_back(n);
reverse(v.begin(), v.end());
for (auto k : v) cout << k << " ";
}
회고
bfs의 경로추적에 대해서 배울 수 있어서 좋은 문제라고 생각합니다. 경로를 구현하는 방법을 숙지하여 이후에 또 다른 구현에 써먹을 수 있도록 내것으로 만들어야 겠다.
문제풀이
간단하게 보면 bfs를 풀면 해결이 될 것으로 생각하였지만, 기존 bfs에서 조금 응용을 해야 문제를 해결할 수 있다. 기존 bfs의 깊이는 새로운 방향을 탐색하여 방문하지 않았다면 깊이를 계속해서 넓혀갔지만, 이 문제는 0인 빈 공간을 만나게 된다면 깊이를 세지않고, 1을 만나게 되면 깊이를 센다고 생각하면 된다.
1. 0은 빈 공간으로써 그냥 지나가야 한다.
2. 친구를 만나게 된다면 쓰러뜨리게 된다.
위에서 한 말이 무엇이냐 하면, Flood Fill 기법을 생각해보면 된다. 0인 공간에서는 색칠을 하지 않지만, 1을 만나게 된다면 인접한 1들을 색칠해준다고 생각해보면 쉽게 해결할 수 있다. 그렇다면 이러한 특정한 위치에만 깊이를 세어야 한다면 큐를 2개 사용해서 해결해보자.
즉 0은 계속해서 탐색하다가, 1을 만나게 되면 또 다른 큐에 1의 위치를 저장한다. 한번 0이 있나 없나 돌아보았으면, 1이 담겨 있는 큐를 또 다시 bfs한다고 생각하면 된다.
#include <bits/stdc++.h>
using namespace std;
int n, m, x_x1, y_y1, x_x2, y_y2;
string arr[301];
int check[301][301];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
queue<pair<int, int>> qu, q;
void bfs(int y, int x) {
qu.push({ y,x });
check[y][x] = 0;
int cnt = 0;
while (arr[x_x2 - 1][y_y2 - 1] != '0') {
cnt++;
while (!qu.empty()) {
int oy = qu.front().first;
int ox = qu.front().second;
qu.pop();
for (int i = 0; i < 4; i++) {
int ny = oy + dy[i];
int nx = ox + dx[i];
if (ny < 0 || ny >= n || nx < 0 || nx >= m || check[ny][nx]) continue;
check[ny][nx] = cnt;
if (arr[ny][nx] != '0') {
arr[ny][nx] = '0';
q.push({ ny,nx });
}
else {
qu.push({ ny,nx });
}
}
}
qu = q;
}
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
cin >> n >> m >> x_x1 >> y_y1 >> x_x2 >> y_y2;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
bfs(x_x1-1,y_y1-1);
cout << check[x_x2 - 1][y_y2 - 1];
}
회고
처음에 문제가 이해가 가질 않았다. 예시를 봐도 단순 bfs로 넓혀져 가는게 아니라는걸 보았는데, 아래의 힌트에서 결과 값을 보고 flood fill이라는걸 깨달았다.
Input
# 0 0 0 0
1 1 1 1 1
0 0 0 0 *
Output
# 0 0 0 0
0 0 0 0 0
0 0 0 0 *
여기서 주난이의 위치에서 bfs를 하게 된다면, 1은 새로운 큐에 들어가게 되고 0은 계속해서 탐색할 것이다. 첫번째 점프에서 현재 상황은 주난이의 위치에서 오른쪽으로 계속해서 0을 쭉 들어가면서 아래에 있는 1은 새로운 큐에 들어간다. 이후 한번의 탐색이 끝나게 된다. 그렇다면 우리는 1을 0으로 색칠을 해줬으니 또 다시 이 새로운 큐를 가지고 계속해서 탐색하게 되는 것이다.
문제풀이
탐색을 하면서 같은 알파벳을 만나게 된다면 다른 길을 탐색하고 현재까지의 최대값을 계속해서 갱신합니다. 간단하게 dfs를 이용하면서 방문지점을 체크하는 bfs의 조합인 브루트포스로 구현할 수 있다.
#include <bits/stdc++.h>
using namespace std;
int r, c;
bool check[100];
bool visited[21][21];
string arr[21];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
int ret = -987654321;
void dfs(int y, int x, int cnt) {
ret = max(ret, cnt);
for (int i = 0; i < 4; i++) {
int ny = dy[i] + y;
int nx = dx[i] + x;
if (ny < 0 || ny >= r || nx < 0 || nx >= c || visited[ny][nx]) continue;
if (check[arr[ny][nx] - 'A']) {
continue;
}
check[arr[ny][nx] - 'A'] = true;
visited[ny][nx] = true;
dfs(ny, nx, cnt + 1);
visited[ny][nx] = false;
check[arr[ny][nx] - 'A'] = false;
}
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
cin >> r >> c;
for (int i = 0; i < r; i++) {
cin >> arr[i];
}
check[arr[0][0] - 'A'] = true;
visited[0][0] = true;
dfs(0, 0, 1);
cout << ret;
}
회고
알파벳을 방문하였으면 그대로 결과 값을 갱신하면서 return하였는데 이는 잘못된 생각임을 알게되었다. 4방향 중 한 방향을 못간다해서 다른 방향을 검사해보지 않는건 말이 안되기 때문이다.
문제풀이
모든 경우를 다 해보면서 가지치기를 하는 백트래킹을 통해 문제를 해결하였다.
#include <bits/stdc++.h>
using namespace std;
int k;
char oper[10];
bool check[10];
vector<string> ret;
bool cmp(char a,char b, char op) {
if (op == '<') {
return a<b;
}
if (op == '>') {
return a>b;
}
}
void go(int index, string num) {
if (index == k + 1) {
ret.push_back(num);
return;
}
for (int i = 0; i < 10; i++) {
if (check[i]) continue;
if (index == 0 || cmp(num[index - 1], i + '0', oper[index])) {
char temp=i+'0';
check[i] = true;
go(index+1,num+temp);
check[i] = false;
}
}
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
cin >> k;
for (int i = 1; i <= k; i++) cin >> oper[i];
go(0, "");
sort(ret.begin(), ret.end());
cout << ret[ret.size() - 1] << "\n" << ret[0];
}
문제풀이
이진트리의 정의
이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다.
깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다.
(아래 그림) 각 노드에는 그 곳에 위치한 빌딩의 번호가 붙여져 있다.
또, 가장 마지막 레벨을 제외한 모든 집은 왼쪽 자식과 오른쪽 자식을 갖는다.
우리가 dfs를 기본적으로 구현하는건 전위순회 방식으로 탐색한다. 전위순회는 루트노드부터 왼쪽자신 오른쪽 자식을 방문하는 것이다. 이 문제에서 요구하는 점은 중위 순회로 왼쪽자식->뿌리->오른쪽 자식으로 방문해야 한다는 것을 알 수 있다. 구현 방법은 재귀로 구현하는데 한번쯤 숙지하는게 좋아보인다.
코드
#include <bits/stdc++.h>
using namespace std;
int k;
int arr[1030];
vector<int> g[11];
void go(int s, int e, int depth) {
if (s >= e) return;
int mid = (s + e) / 2;
g[depth].push_back(arr[mid]);
go(s, mid, depth + 1);
go(mid + 1, e, depth + 1);
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
cin >> k;
for (int i = 0; i < pow(2, k) - 1; i++) {
cin >> arr[i];
}
go(0, pow(2, k) - 1, 0);
for (int i = 0; i < k; i++) {
for (auto k : g[i]) {
cout << k << " ";
}
cout << "\n";
}
}
문제풀이
로직을 생각하기 전에 문제를 먼저 이해하자. 바다인 부분들을 빙산이 만나게 된다면 빙산이 녹는다. 문제의 예시에 정확히 설명이 되어있다. 그렇다면 빙산이 두개로 나눠지는 시점을 어떻게 알까?
bfs를 하면서 어떠한 조건이상인 부분을 찾아야 한다라는 문제는 어떠한 조건을 기준으로 bfs를 돌려서 개수를 카운팅 해주면된다. 그렇다면 여기서의 조건은 빙산이 두 가지로 나눠지는 부분이다. 즉 빙산을 기준으로 bfs를 돌려주면 된다.
종료조건
1. 빙산이 다 녹았지만, 두 개 이상의 덩어리로 분리되지 않을 때 0을 출력
2. 빙산이 두 개 이상의 덩어리로 분리되었을 경우 년도 출력
코드
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[301][301];
bool check[301][301];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
queue<pair<int, int>> qu;
int ret;
void bfs(int y, int x) {
qu.push({ y,x });
check[y][x] = true;
while (!qu.empty()) {
int oy = qu.front().first;
int ox = qu.front().second;
qu.pop();
for (int i = 0; i < 4; i++) {
int ny = dy[i] + oy;
int nx = dx[i] + ox;
if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
if (check[ny][nx]) continue;
if (arr[ny][nx] == 0) {
if (arr[oy][ox] > 0) {
arr[oy][ox] -= 1;
}
}
else {
qu.push({ ny,nx });
check[ny][nx] = true;
}
}
}
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
}
}
while (true) {
int cnt = 0;
bool flag = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] != 0 && !check[i][j]) {
flag = true;
bfs(i, j);
cnt++;
}
}
}
ret++;
if (cnt >= 2) {
cout << ret-1;
break;
}
if (!flag&&cnt<2) {
cout << 0;
break;
}
memset(check, false, sizeof(check));
}
}
회고
마지막에 정답 출력문에서 조금 시간이 걸렸는데, 두 가지 이상의 묶음 빙산이 생기는 시점은 항상 bfs를 한번 더 탐색하여 두 가지 이상인지 알 수 있으니 마지막 출력에는 1년을 빼줘야한다.
문제풀이
맥주를 20개 가지고 한 개당 50m갈 수 있다. 그렇다면 1000m 이내면 모든 경로를 갈 수 있다고 볼 수 있다. 그렇다면 모든 정점에 대해서 거리를 조회할 수 있는 플로이드 와샬을 사용하여 문제를 풀었다. 이 알고리즘은 O(N^3) 10^6 으로 TC=50 => 5*10^7 충분히 시간내에 가능하다.
1000m 이하인 경로가 존재한다면 1을 저장
그 외의 경로는 0을 저장
플로이드 와샬을 사용할 때 두 점 사이의 거리가 1000m 이하인지만 판단해보자. 그렇다면 정점 (i,j)가 1인 경우만 고려하면 된다. i->j가 다이렉트로 되어 있는 경우와 (i->k->j)인 경우 둘 중 하나만 1이라면 맥주를 마시며 이동할 수 있다.
코드
#include <bits/stdc++.h>
using namespace std;
int d[102][102];
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<pair<int, int>> v;
for (int i = 0; i < n + 2; i++) {
int x, y;
cin >> x >> y;
v.push_back({ x,y });
}
for (int i = 0; i < v.size(); i++) {
for (int j = 0; j < v.size(); j++) {
int distance = abs(v[i].first - v[j].first) + abs(v[i].second - v[j].second);
if (distance > 1000) {
d[i][j] = 0;
}
else d[i][j] = 1;
}
}
for (int k = 0; k < v.size(); k++) {
for (int i = 0; i < v.size(); i++) {
for (int j = 0; j < v.size(); j++) {
d[i][j] = d[i][j] | (d[i][k] & d[k][j]);
}
}
}
if (d[0][v.size()-1] == 1) {
cout << "happy"<<"\n";
}
else cout << "sad"<<"\n";
memset(d, 0, sizeof(d));
}
}
회고
플로이드 와샬문제를 좀 더 풀면서 문제에 대한 감을 익히도록 해야겠다.