[풀이]백준 풀이(XII/2573 등 )
문제풀이
빙산(2573, dfs/bfs)
- 2차원배열 (빙산의 높이 저장)
- 동/서/남/북에 있는 0(빙하x, 바다) 만큼 매년 빙하의 높이가 줄어든다.
-
한 덩이의 빙산이 주어지는데 이것이 두 개 이상의 빙산으로 분리되는 최초의 시간을 구하시오.
- 감소시킨 다음에 그룹이 여러개가 되면 출력하자.
회고
- bfs특성상 1년이 흘러 빙하가 줄어드는것을 구현하는데 에러가 조금 있었다.
- 특수케이스 (3,3 0 0 0 /3 1 3/ 0 0 0) 같은 것을 구현해야했다.
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;
int n, m, timeRunidx=0;
int ice[300][300];
int group[300][300];
bool flag = false;
bool iceVisited[300][300];
int dx[] = {0, 0, 1,-1};
int dy[] = {1,-1, 0, 0};
void init(){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
ice[i][j] = 0;
iceVisited[i][j] = false;
}
}
}
void initCheck(){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
iceVisited[i][j] = false;
}
}
}
bool isInside(int x, int y ){
if(x>=0 && y>=0 && x<n && y<m) return true;
else return false;
}
void timeRun(int sx, int sy){
int cx, cy,idx;
queue<pair<int,int>> q;
queue<tuple<int,int,int>> t;
q.push(make_pair(sx,sy));
iceVisited[sx][sy] = true;
while(!q.empty()){
pair<int,int> c = q.front();
q.pop();
cx = c.first;
cy = c.second;
idx = 0;
//1년이 지남(1칸)
for(int i=0; i<4; i++){
int nx = cx+dx[i];
int ny = cy+dy[i];
//바다가 있으면 idx 추가
if(ice[nx][ny]==0 && isInside(nx,ny))
{
idx++;
}
}
//위치정보와 빙하값 큐에 넣기
if(idx>0) t.push(tuple<int,int,int>(cx,cy,idx));
//다음빙하
for(int i=0; i<4; i++){
int nx = cx + dx[i];
int ny = cy + dy[i];
//다음 빙하를 찾자 && 방문한 적 없으면
if(ice[nx][ny]>0 && !iceVisited[nx][ny] && isInside(nx,ny)){
q.push(make_pair(nx,ny));
iceVisited[nx][ny] = true;
}
}
}
//문제발생! 뺄 때 한번에 빼야한다.
//OKAY
while(!t.empty()){
int size = t.size();
for(int a=0; a<size; a++){
int mx, my, mdx;
tuple<int,int,int> k = t.front();
t.pop();
tie(mx,my,mdx) = k;
// cout <<"mx is " << mx << endl;
// cout <<"my is " << my << endl;
// cout <<"mdx is " << mdx << endl;
if(ice[mx][my]-mdx>0) ice[mx][my]-=mdx;
else ice[mx][my]=0;
}
}
// cout << "timeRunidx is " << timeRunidx << endl;
// for(int i=0; i<n; i++){
// for(int j=0; j<m; j++){
// cout << ice[i][j]<< " ";
// }
// cout << endl;
// }
}
bool zeroCheck(){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(ice[i][j]>0) return false;
}
}
return true;
}
int main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
init();
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin >> ice[i][j];
}
}
//전체 search하면서 timeRun 1회 실행
bool b = true;
while(b){
if(zeroCheck()) {
b=false;
break;
}
int timeRunidxTemp = timeRunidx;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(ice[i][j]>0 && !iceVisited[i][j]) {
//만약 한주기에 timeRun이 2회 이상 시작되었다면 break;
if(timeRunidxTemp<timeRunidx) {
b=false;
break;
}
timeRun(i,j);
timeRunidx++;
}
}
}
initCheck();
}
//왜 zchk걸림?
//예외2 한번돌았는데 전부 없어진 경우
if(zeroCheck()) cout << 0;
else
{
if(timeRunidx>=2) cout << timeRunidx-1;
else if(timeRunidx==1) cout << 0;
}
}
토마토 (7576, bfs)
- n*m 2차원 배열
- 익은토마토/안익은토마토가 들어있다.
- 하루가 지나면 익은토마토에 인접한 안익은토마토는 익게된다.
- 혼자 익는 경우는 없으며 최소 몇일 뒤 모두 익을까?
https://www.acmicpc.net/board/view/31423
https://www.acmicpc.net/board/view/27426
https://www.acmicpc.net/board/view/24740
- 입력 형식을 잘 보세요. M, N 순으로 주어지고, M = 가로, N = 세로입니다. 코드의 모든 부분이 이 순서를 지키고 있는지 확인하세요. 변수 이름은 문제에서 주어진 그대로 사용하기를 권장합니다. 그래야 헷갈리지 않습니다.
- 큐의 크기는 최소 100만이 되어야 합니다. 1000*1000 칸 모두가 BFS의 타겟이 될 수 있습니다. 임의로 1000칸이나 10000칸 정도로 잡고 이 정도면 충분하겠지 생각하면 안 됩니다. 또한 정답 역시 약 50만에 달하는 것이 가능합니다 (short로 담을 수 없습니다). 길이 지그재그로 나있는 경우를 생각해 보세요.
- BFS의 방문 여부 기록은 큐에서 뺀 뒤가 아닌, 큐에 넣을 때 하는 것이 바람직합니다. 이미 다른 칸으로부터 방문하기로 예정한 칸의 정보를 또 갱신하거나, 한 좌표가 큐에 중복해서 삽입되는 것은 좋지 못한 결과를 낳을 가능성이 큽니다. 큐에 넣는 순간에 바로 방문 체크를 합시다.
- 인덱스가 배열 범위를 넘어가지 않는지 잘 확인합시다. 배열 범위를 벗어나는 칸에 단 한 번이라도 접근하려고 한다면 언제든 문제가 생길 수 있습니다. 이 때에도 1번에서 설명했듯이 가로, 세로를 헷갈리지 않아야 합니다.
회고
시간초과,,, 좀 더 봐야할 것 같다 ^^…. 생각보다 범위가 엄청커서!
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
int visited[1001][1001];
int tomato[1001][1001];
int n, m, Answer =0;
int dx[] = {0, 0, 1,-1};
int dy[] = {1,-1, 0, 0};
queue<pair<int,int>> q;
queue<pair<int,int>> ripeTemp;
pair<int,int> c;
pair<int, int> tmp;
void init(){
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
tomato[i][j] = 0;
visited[i][j] = false;
}
}
}
void initCheck(){
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
visited[i][j] = false;
}
}
}
void ripe(){
//토마토 익히기
while(!ripeTemp.empty()){
pair<int,int> ntmt = ripeTemp.front();
ripeTemp.pop();
int x = ntmt.first;
int y = ntmt.second;
tomato[x][y] = 1;
}
}
bool zCheck(){
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(tomato[i][j]==0) return true;
}
}
return false;
}
//모두 1인지 체크
bool oneCheck(){
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(tomato[i][j]==0 || tomato[i][j]==-1) return false;
}
}
return true;
}
bool isTomato(){
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(tomato[i][j]==0) return true;
if(tomato[i][j]==1) return true;
}
}
return false;
}
bool isInside(int x, int y ){
if(x>=0 && y>=0 && x<m && y<n) return true;
else return false;
}
void bfs(int sx, int sy){
int cx, cy, nx, ny;
q.push(make_pair(sx,sy));
visited[sx][sy] = true;
//cout << "sx is " << sx << endl;
//cout << "sy is " << sy << endl;
while(!q.empty()){
c = q.front();
q.pop();
cx = c.first;
cy = c.second;
//하루가 지남
for(int i=0; i<4; i++){
nx = cx+dx[i];
ny = cy+dy[i];
//안익은 토마토가 근처에 있으면
if(tomato[nx][ny]==0 && isInside(nx,ny))
{
tmp = make_pair(nx,ny);
ripeTemp.push(tmp);
}
}
}
}
int main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
cin >> n>> m;
init();
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
cin >> tomato[i][j];
}
}
//입력 확인 완료
// for(int i=0; i<m; i++){
// for(int j=0; j<n; j++){
// cout << tomato[i][j] << " ";
// }
// cout << endl;
// }
bool wf = true;
//종료조건3. 토마토가 없다.(입장x)
//종료조건5. 안익은 토마토가 없다.(입장x)
if(!isTomato() or oneCheck()){
wf=false;
Answer = -1;
}
while(wf){
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
//방문하지 않은 익은토마토 전체 방문 후 근처정보 싹담아놓기
if(tomato[i][j]==1 && !visited[i][j])
{
//이게 너무 많이도네.
bfs(i,j);
}
}
}
//모든토마토가 1이면
if(oneCheck())
{
wf=false;
break;
}
//모두 1은 아니고
else
{
//익힐 토마토가 있으면
if(!ripeTemp.empty()){
ripe();
//방문한 곳 초기화
initCheck();
Answer++;
}
//익힐놈도 없는데
else{
//종료조건2. 덜익힌놈이 있다. (0이 남음..)
//ㅇ종료조건4. 안익은 것만 있다. (-1출력, if(zCheck()) 에서 거름
if(zCheck()) Answer=-1;
//ㅇ종료조건1. 깔끔하게 다익혔다. (Answer,if(zCheck()) 안가고 끝남
wf = false;
break;
}
}
}
cout << Answer;
}
댓글남기기