글 읽기 - 반복문 질문

djgjdgjd 6년 전 0

아래 코드에서 bfs함수 while문 안에 주석처리한 부분에 반복문을 없애면 왜 결과가 틀리게 나오는 지 모르겠습니다ㅠ 구조적으로 이해가 안되네여;

#include <cstdio>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

int map[101][101][101];
int check[101][101][101];
int n, m, h, maxV = 0, cnt = 0;
int dh[6] = {0,0,0,0,-1,1};
int dx[6] = {-1,1,0,0,0,0};
int dy[6] = {0,0,-1,1,0,0};
queue< pair<int, pair<int, int> > > q;
int ret = 1;

int bfs()
{
    while(!q.empty()) 
    {
        int size = q.size();
       
        for(int i=0;i<size;i++) // <- 이 반복문을 안거치면 안되는 이유?
            {
                int f = q.front().first;
                int x = q.front().second.first;
                int y = q.front().second.second;
                q.pop();
        
                for(int j=0;j<6;j++)
                {
                    int nf = f + dh[j];
                    int nx = x + dx[j];
                    int ny = y + dy[j];
            
                    if(nf < 0 || nf >= h || nx < 0 || ny < 0 || nx >= n || ny >= m
                       || map[nf][nx][ny] == -1)
                        continue;
                    
                    if(!check[nf][nx][ny] && map[nf][nx][ny] == 0)
                    {
                        check[nf][nx][ny] = 1;
                        map[nf][nx][ny] = 1;
                        q.push(make_pair(nf, make_pair(nx, ny)));
                        cnt--;
                    }
                
        
                if(cnt == 0)
                    return ret;
    
                }
            }
            ret++;
    }
    return -1;
}

int main()
{
    cin>>m>>n>>h;
    
    for(int k=0;k<h;k++)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                cin>>map[k][i][j];
                if(map[k][i][j] == 0)
                    cnt++;
                
                else if(map[k][i][j] == 1)
                    q.push(make_pair(k, make_pair(i, j)));
            }
        }
    }
    
    if(cnt == 0)
    {
        cout<<0<<'\n';
        return 0;
    }

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

kdk8361 6년 전 1

예를 들어보겠습니다.

queue 안에 ret 턴째에 익은 토마토 집합이 4개가 있다고 합시다.

size = q.size()이므로 7이 되며 해당 루프를 도는 동안 queue는

{ret, ret, ret, ret}

{ret, ret, ret} -> q.pop

{ret, ret, ret, ret+1, ret+1, ret+1} -> 해당 위치 주변에 익을 수 있는 토마토가 3개인 경우

{ret, ret, ret+1, ret+1, ret+1} -> q.pop

....

{ret+1, ..... ret+1}

다음 size는 남은 ret+1의 개수가 되겠죠?

이런식으로 진행이 됩니다. queue의 크기는 늘어가지만 우리에게 필요한건 step이 동일한 초기의 4개이므로 저런식으로 size를 이용하는 거죠.

djgjdgjd 6년 전 1

아ㅋㅋㅋ 네 이해했습니다 감사합니다. 근데 제가 for문을 두개를 안쓰고 하나만 써서 해결하고 싶은데 혹시 조언해주실수 있나요??

kdk8361 6년 전 1

check에 들렀나 안들렀나를 저장하는게 아니라 몇번째로 들렀나를 저장하는 방식으로 하시면

while(queue)

for i=0 < 6

이런식으로 하나만 쓰실 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반복문 질문

djgjdgjd 6년 전 0

kdk8361 6년 전 1

djgjdgjd 6년 전 1

kdk8361 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말