백준 7569번 토마토
어제 토마토 (2차원)을 풀었다. 오늘 푼 문제는 거의 비슷한데 3차원으로 구현하는 문제다. 저번주에 dp를 공부할 때 dp문제인 줄 알고 열심히 하다가... 아님을 알고 울면서 ㅜ포기했다.
이 문제가 bfs인 이유는 기본적으로 토마토의 상태를 탐색해주어야 하기 때문이다. 토마토의 상태를 탐색하고, 바꾸어주는것이 관건이므로 토마토의 기본 상태에서 변화해가는 좌표를 기억해가며 탐색해야 한다.
일주일 전에 틀린 코드를 다시 보니 dp가 아니라 큐로 좌표를 저장해가며 대충 구현은 했다. 그러나 중간에 계속 dp인것에 신경이 쓰여(이 문제가 dp문제집에 있었거든......) 머리가 터져버렸다. 정작 코드에는 dp로 구현 안해놓고 왜 dp에 얽매인거지? 이전 코드의 문제점은 토마토가 다 칠해지는 일 수를 구하는 과정이 잘못되었다.
bfs배우고 나서 다시 푸니 별로 어렵지 않았다. 3차원이라서 처음에 토마토의 초기 상태를 입력받는 것이 헷갈렸다.
코드 길이는 dp보다 길긴 해도 구현하는 과정이 재미있다. 이 문제에서 tuple을 처음 써봤다.
#include<stdio.h>
#include<queue>
#include<tuple> //get<0>(t);
using namespace std;
int m, n, h; int greentomato = 0;
int redtomato = 0;
int arr[105][105][105];
queue<tuple<int,int,int>> q;
int make_red(int i, int j, int k) {
int sum = 0;
if (arr[i - 1][j][k] == 0 && i - 1 > 0) {
sum++; arr[i - 1][j][k] = 1; q.push({ i - 1,j,k });
}
if (arr[i + 1][j][k] == 0 && i + 1 <= m) {
sum++; arr[i + 1][j][k] = 1; q.push({ i + 1,j,k });
}
if (arr[i][j + 1][k] == 0 && j + 1 <= n) {
sum++; arr[i][j + 1][k] = 1; q.push({ i,j + 1,k });
}
if (arr[i][j - 1][k] == 0 && j - 1 > 0) {
sum++; arr[i][j - 1][k] = 1; q.push({ i,j - 1,k });
}
if (arr[i][j][k - 1] == 0 && k - 1 > 0) {
sum++; arr[i][j][k - 1] = 1; q.push({ i,j,k - 1 });
}
if (arr[i][j][k + 1] == 0 && k + 1 <= h) {
sum++; arr[i][j][k + 1] = 1; q.push({ i,j,k + 1 });
}
greentomato = greentomato - sum;
return sum;
}
int bfs() {
if (greentomato == 0) return 0;
int day = 0; int prevday = q.size();
int sum = 0;
tuple<int, int, int> t;
while (q.empty()==false) {
while (prevday > 0) {
t = q.front();
sum += make_red(get<0>(t), get<1>(t), get<2>(t));
q.pop();
prevday--;
}
prevday = sum; sum = 0;
day++;
}
if (greentomato > 0) return -1;
return day - 1;
}
int main() {
scanf("%d%d%d", &m, &n, &h);
int t;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= m; k++) {
scanf("%d", &t);
arr[k][j][i] = t;
if (t == 0) greentomato++;
if (t == 1) {
q.push({ k,j,i }); redtomato++;
}
}
}
}
int day = bfs();
printf("%d", day);
}
11724번 연결 요소의 개수
connected component!!
제출 하지않고 혼자 반례를 찾아보는 과정에서 수정할 부분을 발견하였다. 반례는 3 1 \n 1 2이다.
기준이 되는 노드를 탐색하고, 이 노드와 연결된 다른 노드들을 탐색하면서 방문노드수를 갱신해주었는데 이 과정에서 방문노드수가 중복으로 체크가 되었다. => 방문노드수를 갱신하는 과정을 수정하고 제출하였다.
//connected components
#include<stdio.h>
#include<queue>
using namespace std;
int n, e; int visitnode = 0;
int arr[1005][1005];
int isvisit[1005];
queue<int>q;
int bfs() {
int cc = 0; q.push(1);
int vn;
while (visitnode < n) {
//vn에서 연결되어있는 노드들을 탐색한다.
while (q.empty() == false) {
vn = q.front();
for (int i = 1; i <= n; i++) {
if (arr[vn][i] == 1 && isvisit[i] == 0) {
//기준 노드와 연결되어 있고 아직 탐색하지 않은 노드인 경우
q.push(i); isvisit[i] = 1;
}
}
visitnode++; isvisit[vn] = 1; q.pop();
}
cc++;
for (int i = 1; i <= n; i++) {
if (isvisit[i] == 0) {
q.push(i);
break;
}
}
}
return cc;
}
int main() {
scanf("%d%d", &n, &e);
int a, b;
for (int i = 1; i <= e; i++) {
scanf("%d%d", &a, &b);
arr[a][b] = 1; arr[b][a] = 1;
}
int sum = bfs();
printf("%d", sum);
}
7562번 나이트의 이동
go부분 함수,,,, 너무 비효율적으로 푸는 듯한 생각이 들었으나 일단 품. 다른 분들 bfs 코드를 참고했을 때 이상한 배열 두개를 선언하는 경우가 많길래 뭐지 했는데.... 갈 수 있는 좌표를 배열에 담아두고, for문으로 돌려주면 훨씬 더 효율적으로 구현 가능하다(사람들 넘 똑똑하셔)
int x_move[8] = {-2,-1,1,2,-2,-1,1,2};
int y_move[8] = {1,2,2,1,-1,-2,-2,-1};
int dy[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int dx[] = {1, 2, 2, 1, -1, -2, -2, -1};
이렇게 이동할 수 있는 좌표의 변화량을 저장해주기!!
맞긴 했지만 우연히 나의 코드의 반례를 잡아낼 예제가 문제에 주어져있었다. 이 예제가 없었으면 수정하느라 시간 더 걸렸을 것 같다. 반례는 시작 좌표와 도달할 좌표가 같은 경우이다. 둘 좌표가 같은 경우에는 이미 도달한 상태이므로 움직일 필요가 없다. 따라서 이 경우에는 답이 0이다 => 항상 특수한 케이스를 넣어보면서 잘 작동하는지 확인해보기
처음에 이 문제를 읽었을 때 dp인줄 알았다. 메모이제이션이 필요하다는 점, 현재 위치로 이동할 수 있는 좌표들에서 최소이동횟수를 비교해서 저장해주는 방식으로 구현 //정리*******
#include<stdio.h>
#include<queue>
using namespace std;
int arr[305][305];
queue<pair<int, int>>q;
int i, xofs, yofs, xofe, yofe;
bool check(int x, int y) {
if (x <= 0 || y <= 0 || x > i || y > i) return false;
return true;
}
int go(int x, int y) {
int sum = 0;
//여기 부분이 비효율적인듯..
if (check(x - 1, y - 2) == true && arr[x - 1][y - 2] == 0) {
q.push({ x - 1,y - 2 }); arr[x - 1][y - 2] = 1; sum++;
}
if (check(x - 2, y - 1) == true && arr[x - 2][y - 1] == 0) {
q.push({ x - 2,y - 1 }); arr[x - 2][y - 1] = 1; sum++;
}
if (check(x + 1, y - 2) == true && arr[x + 1][y - 2] == 0) {
q.push({ x + 1,y - 2 }); arr[x + 1][y - 2] = 1; sum++;
}
if (check(x + 2, y - 1) == true && arr[x + 2][y - 1] == 0) {
q.push({ x + 2,y - 1 }); arr[x + 2][y - 1] = 1; sum++;
}
if (check(x - 1, y + 2) == true && arr[x - 1][y + 2] == 0) {
q.push({ x - 1,y + 2 }); arr[x - 1][y + 2] = 1; sum++;
}
if (check(x - 2, y + 1) == true && arr[x - 2][y + 1] == 0) {
q.push({ x - 2,y + 1 }); arr[x - 2][y + 1] = 1; sum++;
}
if (check(x + 1, y + 2) == true && arr[x + 1][y + 2] == 0) {
q.push({ x + 1,y + 2 }); arr[x + 1][y + 2] = 1; sum++;
}
if (check(x + 2, y + 1) == true && arr[x + 2][y + 1] == 0) {
q.push({ x + 2,y + 1 }); arr[x + 2][y + 1] = 1; sum++;
}
return sum;
}
void bfs() {
if (xofe == xofs && yofe == yofs) {
printf("0\n"); return;
}
q.push({ xofs,yofs }); arr[xofs][yofs] = 1;
pair<int, int> visitnode;
int sum = 1; int prevsum = 0;
int move = 0;
while (q.empty() == false) {
while (sum > 0) {
visitnode = q.front();
prevsum += go(visitnode.first, visitnode.second);
q.pop();
sum--;
}
sum = prevsum; prevsum = 0;
move++;
if (arr[xofe][yofe] == 1) break;
}
printf("%d\n", move);
}
void init_setting() {
for (int x = 1; x <= i; x++) {
for (int y = 1; y <= i; y++) {
arr[x][y] = 0;
}
}
while (q.empty() == false) q.pop();
}
int main() {
int t; scanf("%d", &t);
for (int u = 1; u <= t; u++) {
scanf("%d%d%d%d%d", &i, &xofs, &yofs, &xofe, &yofe);
init_setting();
xofs++; yofs++; xofe++; yofe++;
bfs();
}
}
2667 단지번호붙이기
구현 중간에 놓친 부분이 있어서 생각보다 시간이 많이 걸린 문제
입력이 첨부한 이미지와 같은 형식인데, 숫자를 입력받을 때 0000111을 하나의 숫자로 보게 된다. 그것을 간과한 채 그냥 띄어쓰기가 있는 것으로 착각하여 그냥 0,1,0 ~~ 이렇게 배열에 담길 것이라고 예상하고 처음에 데이터를 잘못 입력받았다.... 확인하라구
또 i, j 기준으로 상하좌우의 좌표를 대각선의 좌표로 잘못 생각했다 => tox, toy 배열 구현 시 잘 체크하자!
//상하좌우 탐색
#include<stdio.h>
#include<vector>
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
int arr[30][30]; int n;
queue<pair<int, int>> q;
int tox[4] = { 0,0,1,-1 };
int toy[4] = { 1,-1,0,0 };
vector<int> v;
void bfs() {
pair<int, int> node;
int x, y; int h = 0;
while (q.empty() == false) {
while (q.empty()==false) {
node = q.front(); h++;
x = node.first; y = node.second;
arr[x][y] = 0;
for (int i = 0; i < 4; i++) {
if (x + tox[i] <= n && x + tox[i] > 0 && y + toy[i] <= n && y + toy[i] > 0 && arr[x + tox[i]][y + toy[i]] == 1) {
q.push({ x + tox[i], y + toy[i] });
arr[x + tox[i]][y + toy[i]] = 0;
}
}
q.pop();
}
v.push_back(h); h = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (arr[i][j] == 1) {
q.push({ i,j }); break;
}
}
if (q.size() > 0) break;
}
}
}
int main() {
string str;
scanf("%d", &n);
int sum = 0;
for (int i = 1; i <= n; i++) {
cin >> str;
for (int j = 1; j <= n; j++) {
arr[i][j] = int(str[j - 1]) - 48;
if (sum == 0 && arr[i][j] == 1) {
q.push({ i,j }); sum = 1;
}
}
}
bfs(); int index = 0;
printf("%d\n", v.size());
//v sort and print ans
sort(v.begin(),v.end());
while (index < v.size()) {
printf("%d\n", v[index]);
index++;
}
}
맞았는데 코드가 너무 복잡해서 다른 분들의 코드를 참고하여 더 깔끔하게 정리했다.
반복되는 부분은 따로 변수를 할당하여 깔끔하게 한다 => 코드 작성 시에도 실수를 줄일 수 있고 직관적이다.
bfs함수 내에서 배열을 탐색하여 배열 내의 1을 찾아 주면서 모든 집의 집합을 찾게 반복할 수도 있지만, 반복문으로 arr을 탐색하면서 1이 나오는 순간마다 bfs를 호출시키면서 집의 집합을 하나씩 찾아가게 구현할 수도 있다 => 코드 길이나 구현 난이도가 달라지진 않지만 더 직관적임.
[새로 알게 된 사실]
%1d를 쓰면 입력받은 정수도 문자 단위로 나누어서 처리가 가능하다. 이 경우 1자씩 입력받는다.
%2d, %3d 모두 가능하다!!
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int arr[30][30]; int n;
queue<pair<int, int>> q;
int tox[4] = { 0,0,1,-1 }; int toy[4] = { 1,-1,0,0 };
vector<int> v;
void bfs() {
pair<int, int> node;
int x, y; int h = 0;
while (q.empty()==false) {
node = q.front();
h++;
x = node.first; y = node.second;
arr[x][y] = 0;
for (int i = 0; i < 4; i++) {
int nx = x + tox[i];
int ny = y + toy[i];
if (nx <= n && nx > 0 && ny <= n && ny > 0 && arr[nx][ny] == 1) {
q.push({ nx, ny });
arr[nx][ny] = 0;
}
}
q.pop();
}
v.push_back(h);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%1d", &arr[i][j]); //서식제어문자
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (arr[i][j] == 1) {
q.push({ i,j }); bfs();
}
}
}
int index = 0;
printf("%d\n", v.size());
sort(v.begin(),v.end());
while (index < v.size()) {
printf("%d\n", v[index]); index++;
}
}
별로 달라진 것은 없지만, 이번 문제의 경우에는 틀린 부분을 빨리 찾지 못해서 검토에 시간이 많이 걸렸다. 그러므로 코드를 짤 때 조금 더 깔끔하고 직관적으로 짜자..!!
2606 바이러스
매우 쉬움
노드 1을 기준으로 connected component를 구해주면 되는 문제
#include<stdio.h>
#include<queue>
using namespace std;
int arr[103][103]; //간선 정보 저장
int isvisit[103];
queue<int>q;
void bfs(int n,int e) {
q.push(1); isvisit[1] = 1;
int nodenum; int sum = 0;
while (q.empty()==false) {
nodenum = q.front();
for (int i = 1; i <= n; i++) {
if (arr[i][nodenum] == 1 && isvisit[i] == 0) {
q.push(i); isvisit[i] = 1;
}
}
sum++;
q.pop();
}
printf("%d", sum - 1);
}
int main() {
int n,e; scanf("%d%d", &n,&e);
int x, y;
for (int i = 1; i <= e; i++) {
scanf("%d%d", &x, &y);
arr[x][y] = 1; arr[y][x] = 1;
}
bfs(n, e);
}
'코딩) PS 공부 [백준]' 카테고리의 다른 글
| PS) 2178, 1697, 18870번 (미로 찾기, 숨바꼭질, 좌표 압축) (0) | 2021.05.14 |
|---|---|
| PS) 1012, 2583, 2468, 2644번 (유기농 배추, 영역 구하기, 안전 영역, 촌수 계산) (0) | 2021.05.13 |
| PS) 백준 12764, 7576, 1260번 (싸지방에 간 준하, 토마토, DFS와 BFS) in c++ (0) | 2021.05.11 |
| PS) 백준 1720번 (타일 코드) 너ㅓㅓㅓㅓㅓㅓㅓ무 하기 싫고 안풀리는날인데 짜증나아 (0) | 2021.05.06 |
| PS) 3/23 공부 시작, 3-4월의 기록 (78sol, 브론즈 5로 시작하다) (0) | 2021.05.05 |
댓글