<Medium> Surrounded Regions (LeetCode : C#)

https://leetcode.com/problems/surrounded-regions/

📕 문제 설명

X랑 O로 이루어진 행렬이 주어질 때 다음 조건을 만족시키는 O만 남긴 행렬 반환

O가 남는 조건
1) O가 테두리에 있는 경우
2) 변환될 수 없는 O가 인접해 있는 경우

• Input
  X와 O로 이루어진 행렬 (char[][])
• Output
  상하좌우가 X로 둘러싸인 O만 남기기 (void, 기존 행렬 수정)

예제

시도 1.

테두리에 있는 O의 x, y를 기준으로 주변을 bfs로 타고가는 방식

실패 out of memory

public class Solution {
    public void Solve(char[][] board) {
         
        int[] dirX = new int[4] {-1, 0, 0, 1};
        int[] dirY = new int[4] {0, 1, -1, 0};
        bool[,] visitedBoard = new bool[board.Length, board[0].Length];
        List<(int, int)> borderList = new List<(int, int)>();

        // 테두리에 있는 O 기준으로 인접한 것만 찾기
        for (int i = 0; i < board[0].Length; i++)
        {
            if (board[0][i] == 'O') borderList.Add((0, i));
            if (board[board.Length - 1][i] == 'O') borderList.Add((board.Length - 1, i));
        }
        for (int i = 1; i < board.Length - 1; i++)
        {
            if (board[i][0] == 'O') borderList.Add((i, 0));
            if (board[i][board[0].Length - 1] == 'O') borderList.Add((i, board[0].Length - 1));
        }

        foreach((int, int) pos in borderList)
        {
            Queue<(int, int)> queue = new Queue<(int, int)>();
            queue.Enqueue((pos.Item1, pos.Item2));
            while (queue.Count >= 1)
            {
                (int, int) currPos = queue.Dequeue();
                visitedBoard[currPos.Item1, currPos.Item2] = true;   
                for (int d = 0; d < 4; d++)
                {
                    int curX = currPos.Item1 + dirX[d];
                    int curY = currPos.Item2 + dirY[d];

                    if (curX >= board.Length || curX < 0 || curY >= board[0].Length || curY < 0) continue;
                    if (visitedBoard[curX, curY]) continue;
                    if (board[curX][curY] == 'O')
                    {
                        queue.Enqueue((curX, curY));
                    }
                }
            }
        }
		// 바꿔야하는 것들 x로 바꾸기
        for (int i = 0; i < board.Length; i++)
        {
            for (int j = 0; j < board[0].Length; j++)
            {
                if (!visitedBoard[i, j] && board[i][j] == 'O') board[i][j] = 'X';
            }
        }
    }
}

풀이

큐로 처리하는 부분이 메모리 쌓이는 문제 있는 것 같아서 DFS로 바꿔서 풀었다. 테두리를 돌면서 O가 있으면 DFS를 돌며 인접한 O들을 처리한다. (로직은 동일)

public class Solution {
    public void Solve(char[][] board) {
        if (board.Length == 1 && board[0].Length == 1) return;
        bool[,] visitedBoard = new bool[board.Length, board[0].Length];
        int[] dirX = new int[4] {-1, 0, 0, 1};
        int[] dirY = new int[4] {0, 1, -1, 0};

        // 테두리에 있는 O 기준으로 인접한 것만 찾기
        for (int i = 0; i < board[0].Length; i++)
        {
            if (board[0][i] == 'O' && !visitedBoard[0, i])
            {
                DFS(0, i);
            } 
            if (board[board.Length - 1][i] == 'O' && !visitedBoard[board.Length - 1, i]) 
            {
                DFS(board.Length - 1, i);
            }
        }
        for (int i = 1; i < board.Length - 1; i++)
        {
            if (board[i][0] == 'O' && !visitedBoard[i, 0])
            {
                DFS(i, 0);
            } 
            if (board[i][board[0].Length - 1] == 'O' && !visitedBoard[i, board[0].Length - 1])
            {
                DFS(i, board[0].Length - 1);
            } 
        }

        void DFS(int x, int y)
        {
            visitedBoard[x, y] = true;
            
            for (int i = 0; i < 4; i++)
            {
                int currX = x + dirX[i];
                int currY = y + dirY[i];

                if (currX < 0 || currY < 0 || currX >= board.Length || currY >= board[0].Length) continue;
                if (visitedBoard[currX, currY]) continue;
                if (board[currX][currY] == 'O')
                {
                    DFS(currX, currY);
                }
            }
        }

        for (int i = 0; i < board.Length; i++)
        {
            for (int j = 0; j < board[0].Length; j++)
            {
                if (!visitedBoard[i, j] && board[i][j] == 'O') board[i][j] = 'X';
            }
        }
    }
}

결과