[LeetCode][DFS|BFS] 130. Surrounded Regions

 

 

문제 링크

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

Surrounded Regions - LeetCode

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

 

 

 

 

문제 해석

 

개인적으로 엄청 싸웠던 문제이다... 계속 무언가 놓치고 있는 듯한 느낌이 들었던 문제 ㅠㅠ

두 가지 방식으로 풀어보았다! 두 방식 모두 mn의 속도를 가지긴 하지만 두 번째 방식이 훨씬 더 빨랐다.

 

mn의 이중 for문을 돌면서 X로 바꿀 곳을 찾아 dfs하는 방식 boundary에 있는 O와 연결된 곳을 먼저 표시한 후 boundary 내부에 있는데 표시가 안되어 있는 곳을 X 로 바꾸기

 

처음에는 정말 단순하게 1번 방식으로 시도했다. 하지만 구멍도 많이 보였고 무언가 힘들게 목적지를 찾아가는 느낌이었다. 보통은 그렇게 시작할듯!? (나만 그럴지도.... ㅎㅎ) 엄청 싸우며 어찌어찌 1번 방식으로 success를 보게 되었는데............

 

1번으로 풀고나니 번뜩 생각나는 2번 방식! 체크하는 순서를 바꾼 것이다.

1. X로 바꿀 애들은 찾다가 boundary와 연결되어 있으면 제외하는 방식이었다면.....
2. 제외될 애들을 먼저 체크하고 나머지를 X로 바꿔줌 !!

 

이렇게 사고를 전환하니 정말... 코드 짜는건 10분도 안 걸렸다... 

깨달음이 많았던 문제!

 

 

 

 

제출 코드

 

2번 방식으로 푼 코드를 첨부하였다. 

우선 좌표를 다루기 위해 Spot이라는 내부 클래스를 정의하였으며 방향을 쉽게 다루기 위해 dir 배열을 선언해 두었다.

코드는 정말 단순하다 (ㅋㅋㅋㅋ) 

1. boundary를 돌면서 연결된 O들을 보고 체크해 주기! (이를 위해 visit을 두었다)
2. boundary 내부를 돌면서 visit 체크가 안 된 O들을 X로 바꿔주기!

class Solution {
    int m = 0;
    int n = 0;
    int[][] dir = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public void solve(char[][] board) {
        m = board.length;
        n = board[0].length;
        boolean[][] visited = new boolean[m][n];

        // col == 0
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                func(board, i, 0, visited);
            }
        }

        // col == n - 1
        for (int i = 0; i < m; i++) {
            if (board[i][n - 1] == 'O') {
                func(board, i, n - 1, visited);
            }
        }

        // row == 0
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                func(board, 0, j, visited);
            }
        }

        // row == m - 1
        for (int j = 0; j < n; j++) {
            if (board[m - 1][j] == 'O') {
                func(board, m - 1, j, visited);
            }
        }
        
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (board[i][j] == 'O' && !visited[i][j]) board[i][j] = 'X';
            }
        }

    }

    private void func(char[][] board, int x, int y, boolean[][] visited) {
        
        visited[x][y] = true;
        
        for (int i = 0; i < 4; i++) {
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            
            if (isOutside(dx, dy) || visited[dx][dy] || board[dx][dy] == 'X') continue;
            
            func(board, dx, dy, visited);
        }
    }

    private boolean isOutside(int x, int y) {
        if (x >= 0 && x < m && y >= 0 && y < n) return false;
        else return true;
    }
    
    class Spot {
        int x;
        int y;
        
        Spot(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

 

 

 

 

제출 결과

 

메모리는 여전히 많이 사용 중 ㅠㅠ 

제출 내역을 살펴보면 2번 방식으로 바꾸자 runtime이 2ms로 훅 떨어진 것을 볼 수 있다!

(10분도 안 걸렸다 했는데 11분 차이가 나네......... 호호)

 

 

 

참고 링크

 

 

 

 

 

 

너무너무 속상하지만.. 이번 문제를 풀면서 알게 된 사실..

C = A || B 에서 A == true이면 B는 돌지 않는다................

이제 알다니..... 바봉가봉가.... 부끄럽다! (쥬륵)

- mushroong

 

 

 

 

---