12/7 풀이

Pacific Atlantic Water Flow

https://neetcode.io/problems/pacific-atlantic-water-flow

NeetCode

 

우선 태평양, 대서양과 인접해있는 좌표들을 각각 큐에 담아주고 BFS를 실행해주며 방문 체크하면 됐다.

 

문제에서 제일 헷갈렸던 부분은 현재 높이보다 다음 지점의 높이가 같거나 크다면 이동가능하다고 생각했는데, 

해당 문제에서의 BFS의 탐색 방식은 이 반대로 현재 위치에서의 물이 어디서 왔는지 탐색하고 있다.

BFS를 돌리고 난 후, 두개의 방문 배열들을 비교해서 교집합만 따로 결과값에 넣어주면 되는 문제였다.

 

Surrounded Regions

https://neetcode.io/problems/surrounded-regions

NeetCode

 

 

 

O가 X안에 갇혀있다면, X로 바꿔주고 만약에 갇혀있지 않다면 그대로 둬야하는 문제다.

 

BFS를 돌려야 하는 부분은,

1. 가장자리가 아닐 것 (바깥에 있다면 갇혀있다는 말 자체가 불가능)

2. 방문이 안되어있고, O인 부분

이 두가지 조건을 만족해야 한다.

 

내가 가장 헷갈렸던 부분은 리스트에 현재 좌표들을 계속 넣어주고, 가장자리에 도달했고 O 라면 전부 방문을 초기화 해줬다.

 

OXXOX
XOOXO
XOXOX
OXOOO
XXOXO

위 예제 일 때,

OXXOX
XXXXO
XXXXX
OXXOO
XXOXO

 

빨간색 값들이 O가 되어야 하는데, 전부 X로 초기화되는 문제가 발생했다. 

내 방식은 모든 배열들을 일괄적으로 초기화를 시켜주기 때문에 연결 여부를 명확하게 판단할 수 없었다.

따라서, 가장자리에 도달했다면 flag를 true 처리해주고,

if (x == 0 || y == 0 || x == board.length - 1 || y == board[0].length - 1) {
    flag = true;
}

 

큐에 빠져나온 시점에서 가장자리를 방문했었다면 방문처리를 초기화 시켜주었다.

if (flag) {
    for(int [] tmps : tmp) {
        visited[tmps[0]][tmps[1]] = false;
    }
}

이렇게 되면 모든 지점을 성공적으로 방문하며 연결 여부를 명확하게 판단할 수 있다.