글 읽기 - 코드 질문

djgjdgjd 5년 전 0

코드의 dfs 함수에서 주석 처리로 물음표 표시한 부분이 이해가 되지 않습니다.

0이었던 값을 1로 만들어 기둥을 세웠던 위치를 다시 0으로 되돌린다는 건 알겠는데

재귀때문에 머리가 아파서 어떻게 돌아가는건지 제대로 이해가 되지 않습니다 ㅠㅠ

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <vector>
#include <functional>
 
#define MAX_SIZE 8
#define INF 0x7fffffff
 
using namespace std;
//input
int map[MAX_SIZE][MAX_SIZE];
int m, n;
 
//process
bool visit[MAX_SIZE][MAX_SIZE];
int max_value;
int dx[4] = { 1, 0, 0, -1 };
int dy[4] = { 0, 1, -1, 0 };
 
vector<pair<int, int> > virus;
 
void input()
{
    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &map[i][j]);
 
            if(map[i][j] == 2) virus.push_back(make_pair(i, j));
        }
    }
}
 
void copy_map(int (*a)[MAX_SIZE], int (*b)[MAX_SIZE])
{
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            a[i][j] = b[i][j];
        }
    }
}
 
int recovery(int (*a)[MAX_SIZE], int (*b)[MAX_SIZE])
{
    int ret = 0;
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(a[i][j] == 0) ret++;
            a[i][j] = b[i][j];
        }
    }
    return ret;
}
 
void bfs()
{
    queue<pair<int, int> > q;
    for(int i = 0; i < virus.size(); i++) q.push(virus[i]);
 
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if(nx < 0 || ny < 0 || nx >= m || ny >= n || map[nx][ny] != 0) continue;
 
            map[nx][ny] = 2;
            q.push(make_pair(nx, ny));
        }
    }
}
 
void dfs(int x, int y, int d)
{
    map[x][y] = 1;
    visit[x][y] = 1;
 
    if(d == 3)
    {
        //bfs
        int tmp[MAX_SIZE][MAX_SIZE];
        copy_map(tmp, map);
 
        bfs();
        max_value = max(max_value, recovery(map, tmp));
 
        visit[x][y] = 0;
        map[x][y] = 0;
        return;
    }
 
    for(int i = x; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(visit[i][j] || map[i][j] != 0) continue;
            dfs(i, j, d + 1);
        }
    }
 
    map[x][y] = 0;      // ?    
    visit[x][y] = 0;    // ?
}
 
void process()
{
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(map[i][j] != 0) continue;
            dfs(i, j, 1);
        }
    }
 
    printf("%d\n", max_value);
}
 
int main()
{
    input();
    process();
 
    return 0;
}

djm03178 5년 전 1

가령 벽을 이렇게 세웠다고 칩시다.

1 1

1 0

그 다음 벽을 세울 수 있는 조합은

1 1

0 1

이겠죠. 그런데 오른쪽 아래에만 벽을 세우면 끝나는 게 아니라, 아까 왼쪽 아래에 세웠던 벽은 없애줘야 합니다. 그 역할을 저 문장들이 합니다.

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

문제

문제

출처

ICPC

코드 질문

djgjdgjd 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말