[백준] 16946 - 벽 부수고 이동하기 4

1. 문제

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

2. 개요

N x M 크기의 맵이 있다.

벽은 1, 빈 곳은 0으로 표현된다.

벽이 위치한 각각의 칸에 대해 그 칸의 벽을 부쉈을 때 갈 수 있는 칸의 개수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

처음에는 각각의 벽에 대해 빈 공간을 찾아들어가는 DFS를 실행해봤으나 시간초과가 떴다.

이미 방문했던 빈 공간을 다시 찾아 들어가기 때문에 시간초과가 생긴 듯 했다.

그래서 먼저 빈 공간에 대한 정보를 갱신한다.

빈 공간을 찾아 DFS로 탐색하며 그 공간들을 Set에 넣어준다.

더이상 인접한 빈 공간이 없다면, Set에 들어있는 각각의 빈 공간의 값을 Set의 길이 * -1로 갱신한다.

다시 이 Set의 공간들을 탐색하면서 이 빈 공간들의 Set에서 아직 방문한 적 없으면서 인접한 벽에 Set의 길이만큼 더해준다.

맵의 모든 구역에 대해 작업을 마쳤다면, 값을 출력한다.

맵의 구역의 값이 0보다 크다면 벽이므로 10을 나눈 나머지값을 출력하고, 그렇지 않다면 빈 공간이므로 0을 출력한다.

3-2. Python

import sys

sys.setrecursionlimit(10000000)

N, M = map(int, sys.stdin.readline().split())

board = []
for i in range(N):
    board.append(list(map(int, sys.stdin.readline().rstrip())))

def DFS(y, x):
    dirY, dirX = [-1, 0, 1, 0], [0, -1, 0, 1]

    for i in range(4):
        nextY, nextX = y + dirY[i], x + dirX[i]

        if nextY < 0 or nextY >= N or nextX < 0 or nextX >= M:
            continue

        if (nextY, nextX) in visited:
            continue

        if board[nextY][nextX] > 0:
            continue

        visited.add((nextY, nextX))
        DFS(nextY, nextX)

def Make(y, x):
    dirY, dirX = [-1, 0, 1, 0], [0, -1, 0, 1]

    for i in range(4):
        nextY, nextX = y + dirY[i], x + dirX[i]

        if nextY < 0 or nextY >= N or nextX < 0 or nextX >= M:
            continue

        if (nextY, nextX) in v:
            continue

        if board[nextY][nextX] < 0:
            continue

        board[nextY][nextX] -= board[y][x]
        v.add((nextY, nextX))

for i in range(N):
    for j in range(M):
        if board[i][j] == 0:
            visited = set()
            visited.add((i, j))
            DFS(i, j)

            visited = list(visited)
            visitedlen = len(visited)
            v = set()
            for k in range(visitedlen):
                board[visited[k][0]][visited[k][1]] = -visitedlen
                Make(visited[k][0], visited[k][1])

for i in range(N):
    for j in range(M):
        print(board[i][j] % 10, end = '') if board[i][j] > 0 else print(0, end = '')
    print()

3-3. C#

namespace boj_16946
{
    internal class Program
    {
        static int N;
        static int M;
        static int[,] board;
        static int[] dirY = { -1, 0, 1, 0 };
        static int[] dirX = { 0, -1, 0, 1 };
        static HashSet<int> visited;
        static HashSet<int> visited2;

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();

            N = int.Parse(input[0]);
            M = int.Parse(input[1]);

            board = new int[N, M];

            for (int i = 0; i < N; i++)
            {
                string row = sr.ReadLine();

                for (int j = 0; j < M; j++)
                {
                    board[i, j] = int.Parse(row[j].ToString());
                }
            }
            
            visited = new HashSet<int>();
            visited2 = new HashSet<int>();
            List<int> visitedList = new List<int>();

            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < M; j++)
                {
                    if (board[i, j] == 0)
                    {
                        visited.Clear();
                        visited.Add(i * 10000 + j);
                        DFS(i, j);

                        visitedList = visited.ToList();
                        visited2.Clear();

                        for (int k = 0; k < visitedList.Count; k++)
                        {
                            board[visitedList[k] / 10000, visitedList[k] % 10000] = -visitedList.Count;
                            Make(visitedList[k] / 10000, visitedList[k] % 10000);
                        }
                    }
                        
                }
            }

            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < M; j++)
                {
                    if (board[i, j] > 0)
                        sw.Write(board[i, j] % 10);
                    else
                        sw.Write(0);
                }
                sw.WriteLine();
            }

            sw.Close();
        }

        static void DFS(int y, int x)
        {
            for (int i = 0; i < 4; i++)
            {
                int nextY = y + dirY[i];
                int nextX = x + dirX[i];

                if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M)
                    continue;

                if (visited.Contains(nextY * 10000 + nextX))
                    continue;

                if (board[nextY, nextX] > 0)
                    continue;

                visited.Add(nextY * 10000 + nextX);
                DFS(nextY, nextX);
            }
        }

        static void Make(int y, int x)
        {
            int[] chk = new int[2];
            for (int i = 0; i < 4; i++)
            {
                int nextY = y + dirY[i];
                int nextX = x + dirX[i];

                chk[0] = nextY;
                chk[1] = nextX;

                if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M)
                    continue;

                if (visited2.Contains(nextY * 10000 + nextX))
                    continue;

                if (board[nextY, nextX] < 0)
                    continue;

                board[nextY, nextX] -= board[y, x];
                visited2.Add(nextY * 10000 + nextX);
            }
        }
    }
}