Surrounded Regions

리트코드에서 재미난 문제를 풀었다. 마지막으로 풀었던 기록을 보니깐 2020년이었는데 입대하기 전에 풀고 지금 다시 풀어봤다. 분명히 이 문제를 풀때 힘든 기억이 있지만 어렴풋이 기억이 나서 풀려고 했는데 테스트 케이스가 너무 쉽게 풀려서 내가 왜 고생했지 라는 생각으로 submit 했지만 바로 에러가 나왔다.

이 문제는 접근 방식을 좀 다르게 생각해야한다. X로 4가지 방향에서 덮히는 구간을 전부 X로 바꿔야 하는데 여기서 가장 자리에 있는 O는 바뀌지 않는 국룰이 있다. 그런데 나는 가운데 구간에서 O이 발견되면은 연결된 모든 구간을 X로 바꾸는 단순한 생각을 했어서 에러가 나왔다.

국룰을 생각할때 가장자리에 있는 O를 기준으로 생각을 해야한다. 가장 자리에 O와 연결된 모든 다른 O는 4가지의 X에 덮힐수 없는 범위다. 그렇기 때문에 그 범위를 A라는 다른 캐릭터로 커버해주고 DFS가 끝나면은 A자리를 제외한 모든 O를 X로 만들어주면 쉽게 문제를 풀 수 있을것이다.

조금은 창의적인 방식으로 푸는 문제였기 때문에 신기해서 기록하고 싶었다.

class Solution {
    public void dfs(int i, int j, char[][] board){
        if(i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != 'O') return; 
        board[i][j] = 'A'; 
        dfs(i+1,j,board);
        dfs(i-1,j,board);
        dfs(i,j+1,board); 
        dfs(i,j-1,board); 
    }
    public void solve(char[][] board) {
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[i].length; j++){
                if(i == 0 || i == board.length-1 || j == 0 || j == board[0].length-1){
                    if(board[i][j] == 'O') dfs(i,j,board); 
                }
            }
        }
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[i].length; j++){
                if(board[i][j] == 'O') board[i][j] = 'X'; 
                if(board[i][j] == 'A') board[i][j] = 'O'; 
            }
        }
    }
}