인프런 커뮤니티 질문&답변

https://www.acmicpc.net/source/53830318

여기있습니당!!

재열님 ㅎㅎ근데 이 코드 맞았다고 뜨는데... 혹시 어떤 부분에서 막혔는지 말씀해주실 수 있을까요? 고민하시다가 맞으신건가요?

정답코드를 보고 왜 이렇게 짜야지 정답일까를 보고 있었는데 (처음 의문) if문에서 return이 되면 go함수가 종료되는것으로 이해하고 있는데 그럼 다시 go함수를 어떻게 반복하지? >> while문이 반복되는건가? >> cnt가 근데 왜 최대 3번까지만 돌아가지? >> 여기서 약간 멘붕이 와서 질문했다가 >> for문에서는 상하좌우 4번을 돌리고 if문에서 return되는것은 상하좌우중 한가지만 리턴이고 다시 go함수(dfs)가 작동되는건가 해서 질문남겼습니다!! ㅜㅜ

음.. 근데 이거는 디버깅하면서 출력해보면 알 수 있는건데요. 제가 재밌게 디버깅코드를 추가해봤어요. 참고부탁드립니다.

#include <bits/stdc++.h>
using namespace std; 
int a[104][104], visited[104][104];
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int n, m, cnt, cnt2;
vector<pair<int, int>> v;

void go(int y, int x){
    visited[y][x] = 1;
    if(a[y][x] == 1){
        v.push_back({y, x});
        return;
    }
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx]) continue; 
        go(ny,nx);
    }
    return;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    while(true){
    	cout << "WHILE문작동\n";
        cnt2 = 0;
        fill(&visited[0][0], &visited[0][0] + 104 * 104, 0);
        v.clear(); 
        go(0, 0);
    	cout << "gogo : " << v.size() << "\n";
        for(pair<int, int> b : v){
            cnt2++;
            a[b.first][b.second] = 0;
        }
        bool flag = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(a[i][j] != 0) flag = 1;
            }
        }
    	cout << "히익 flag : " << flag << "\n";
        cnt++;
    	cout << "cnt : " << cnt << "\n";
        if(!flag) break;
    }
    cout << cnt << '\n' << cnt2 << '\n';
    return 0;
}
/*
WHILE문작동
gogo : 31
히익 flag : 1
cnt : 1
WHILE문작동
gogo : 22
히익 flag : 1
cnt : 2
WHILE문작동
gogo : 5
히익 flag : 0
cnt : 3
3
5
*/

go 함수가 실행되면 (y,x)좌표가 4방향으로 탐색할때, 상, 우, 하, 좌 를 탐색하는데 예를 들어 상을 탐색할 때는 1이 아니라 go(ny,nx)형태로 넣는다고 하고, 우를 탐색할때 1이면 '녹일 치즈의 위치'를 가지는 v에 넣어주고 리턴합니다. 그럼 상, 우,는 끝났고 아직 하, 좌 가 남았으니 계속 실행합니다.
저도 배우는 입장이라 틀렸을 수도 있지만 제가 이해한 논리는 그렇습니다!

근데 또 의문인게 만약 상하좌우에서 그게 발생되는거라면 if문 자체가 for문 안쪽에 있는게 맞지 않을까요!?? 근데 디버깅해보면 공부합시다님의 생각이 맞는것 같습니당