[백준] 16946번 : 벽 부수고 이동하기 4 - C++ / JAVA

백준 16946 : 벽 부수고 이동하기 4

등급 : Gold II

16946번: 벽 부수고 이동하기 4 (acmicpc.net)

16946번: 벽 부수고 이동하기 4

사용 알고리즘 : DFS

사용 자료구조 : Vector

 

벽의 위치에서 벽을 부수고 이동할 수 있는 공간을 구하는 문제.

주어진 그래프가 있을 때, 영역 별 크기의 합을 미리 구하고, 벽과 인접한 영역들의 값을 더해주는 방법으로 풀이 가능.

이때 인접한 곳은 상하좌우로 확인하는데, 그림과 같이 중복되는 경우에 두 번 더해질 수 있으므로, 방문 정보를 기록한다.

---

  1. DFS를 구현하여 0인 곳을 탐색하고, visit 배열에 각 위치의 영역 번호(mark)를 기록한다.

       ( DFS가 한 번 끝나면 mark를 증가시키는 방법으로 진행 )  

  2. 인덱스 번호에 맞춰 영역별 크기를 벡터에 저장해준다. (1번 영역은 loc[1]과 같은 방식)

  3. 영역의 크기에 맞춰 방문 정보를 저장할 동적 배열을 생성해준다.

  4. 모든 벽을 탐색하며, 상하좌우의 mark정보를 가져오고, mark에 해당하는 크기 값을 더해준다.

       → 이때 앞서 만든 방문 정보를 저장하는 배열을 활용해 두 번 방문하지 않도록 해 준다.

  5. 값을 10으로 나눈 나머지를 출력해준다.

      ( 그래프 자체에 10으로 나눈 값을 저장하게 되면, 1이 되는 경우 추가로 탐색하게 되는 오류가 발생할 수 있으므로 수정하지 않는다. )

---

<hide/>
#include <iostream>
#include <vector>

using namespace std;

int n, m;
int tmp;
int mark = 1;
vector <vector <int>> v;
vector <int> loc;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int visit[1001][1001] = { 0 };

void dfs(int x, int y, int cur_mark)
{
    visit[x][y] = cur_mark;
    tmp++;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < n && ny < m)
        {
            if (visit[nx][ny] == 0 && v[nx][ny] == 0)
            {
                dfs(nx, ny, cur_mark);
            }
        }
    }

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    v.resize(n, vector<int>(m));
    string x;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        for (int j = 0; j < m; j++)
        {
            v[i][j] = x[j] - '0';
        }
    }
    loc.push_back(-1);
    // 인덱스 번호를 맞춰주기 위해 가장 앞에 버리는 값을 저장.
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (v[i][j] == 0 && visit[i][j] == 0)
            {
                tmp = 0;
                dfs(i, j, mark);
                loc.push_back(tmp);
                mark++;
            }
        }
    }
    bool* chk_loc = new bool[loc.size()]{false};
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (v[i][j] == 1)
            {
                for (int k = 0; k < 4; k++)
                {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (nx >= 0 && ny >= 0 && nx < n && ny < m)
                    {
                    	if(!chk_loc[visit[nx][ny]] && v[nx][ny] == 0)
                        {
                        	v[i][j] += loc[visit[nx][ny]];
                        	chk_loc[visit[nx][ny]] = true;
                        }
                    }
                }
                fill_n(chk_loc, loc.size(), false);
            }
            cout << v[i][j] % 10;
        }
        cout << "\n";
    }
}

<hide/>
import java.io.*;
import java.util.*;

public class Main {
    static int n, m, tmp;
    static List<List<Integer>> v = new ArrayList<>();
    static List<Integer> location = new ArrayList<>();
    static int[][] visit = new int[1001][1001];
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static void dfs(int x, int y, int cur_mark)
    {
        visit[x][y] = cur_mark;
        tmp++;
        for(int i=0; i<4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx>=0 && ny>=0 && nx<n && ny < m)
            {
                if(visit[nx][ny] == 0 && v.get(nx).get(ny) == 0)
                {
                    dfs(nx, ny, cur_mark);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        for(int i=0; i<n; i++)
        {
            String x = br.readLine();
            v.add(new ArrayList<>());
            for(int j=0; j<m; j++)
            {
                v.get(i).add(x.charAt(j) - '0');
            }
        }
        int mark = 1;
        location.add(-1);
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(v.get(i).get(j) == 0 && visit[i][j] == 0)
                {
                    tmp = 0;
                    dfs(i, j, mark);
                    location.add(tmp);
                    mark++;
                }
            }
        }
        boolean[] chk_loc = new boolean[location.size()];
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                int ans = 1;
                if(v.get(i).get(j) == 0)
                {
                    sb.append(0);
                }
                else
                {
                    for(int k=0; k<4; k++)
                    {
                        int nx = i + dx[k];
                        int ny = j + dy[k];

                        if(nx >=0 && ny >=0 && nx<n && ny<m)
                        {
                            if(!chk_loc[visit[nx][ny]] && v.get(nx).get(ny) == 0)
                            {
                                chk_loc[visit[nx][ny]] = true;
                                ans+=location.get(visit[nx][ny]);
                            }
                        }
                    }
                    sb.append(ans % 10);
                    Arrays.fill(chk_loc, false);
                }
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}