리트코드 75 9일 차, BFS, DFS 문제 패턴을 풀어봤다.
994. Rotting Oranges
m x n 배열이 주어졌을 때 값은 0, 1, 2 세 종류의 값 중 하나를 가진다. 0은 빈칸, 1은 신선한 오렌지, 2는 썩은 오렌지를 의미한다. 매 분마다 동서남북으로 썩은 오렌지에 인접한 신선한 오렌지는 썩게 된다. 신선한 오렌지가 존재하지 않을 때까지 걸리는 시간(분)을 리턴해야 한다. 만약 불가능하다면 -1을 리턴한다.
You are given an m x n grid where each cell can have one of three values:
0 representing an empty cell,1 representing a fresh orange, or2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
배열을 순회하면서 신선한 오렌지 갯수를 카운트하고, 썩은 오렌지들은 큐에 넣고 BFS로 썩은 오렌지 주변에 있는 신선한 오렌지를 찾는다. 큐에 썩은 오렌지를 넣을 때는 그 오렌지가 썩은 시간을 함께 저장해서 다음 오렌지가 썩는 시간을 계산할 수 있게 한다. 최종적으로 신선한 오렌지를 전부 찾았다면 신선한 오렌지가 없을 것이므로 fresh=0일 것이다. 그러면 걸린 시간(ret)을 리턴하고, 아니라면 -1을 리턴한다.
class Solution {
private int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static class Orange {
int r;
int c;
int step;
public Orange(int r, int c, int step) {
this.r = r;
this.c = c;
this.step = step;
}
}
public int orangesRotting(int[][] grid) {
Queue<Orange> q = new LinkedList<>();
int ret = 0;
int fresh = 0;
for(int r=0; r<grid.length; r++) {
for(int c=0; c<grid[0].length; c++) {
if (grid[r][c] == 2) {
// rotten
q.offer(new Orange(r, c, 0));
} else if (grid[r][c] == 1) {
fresh++;
}
}
}
while(!q.isEmpty()) {
Orange orange = q.poll();
for(int[] dir : dirs) {
int newr = orange.r + dir[0];
int newc = orange.c + dir[1];
if (newr >= 0 && newr < grid.length &&
newc >= 0 && newc < grid[0].length &&
grid[newr][newc] == 1) {
fresh--;
q.offer(new Orange(newr, newc, orange.step+1));
grid[newr][newc] = 2;
}
}
ret = Math.max(ret, orange.step);
}
if(fresh == 0) {
return ret;
}
return -1;
}
}m x n 배열을 한번 순회하면서 O(mn), 배열에 오렌지가 모두 들어가 있는 경우 mn개를 순회하게 되므로 시간 복잡도는 O(mn),
공간 복잡도는 최악의 경우 큐에 mn개의 원소가 들어갈 수 있으므로 O(mn).
841. Keys and Rooms
0부터 n-1번째까지 n개의 방이 있다. 0번째 방은 열려있고 나머지 방은 들어가는데 키가 필요하다. 방에는 방 번호가 쓰인 열쇠들이 있다. rooms[i]는 i번째 방에서 얻을 수 있는 열쇠 리스트를 나타낸다. 모든 방을 들어갈 수 있다면 true를 리턴하고, 아니면 false를 리턴하라.
There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.
When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.
Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.
0번째 방이 열려있기 때문에 rooms[0]에서 시작해서 들어갈 수 있는 모든 방을 순회하고, 모두 방문한 경우 true, 그렇지 않으면 false를 리턴한다. 직관적인 문제라 어렵진 않았다.
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
boolean[] visited = new boolean[rooms.size()];
visited[0] = true;
dfs(rooms, visited, 0);
for (boolean visit : visited) {
if (!visit) {
return false;
}
}
return true;
}
private void dfs(List<List<Integer>> rooms, boolean[] visited, int idx) {
List<Integer> keys = rooms.get(idx);
for(int key : keys) {
if (!visited[key]) {
visited[key] = true;
dfs(rooms, visited, key);
}
}
}
}n개의 방을 방문하기 때문에 시간 복잡도는 O(n)일 것으로 생각했는데, 방에 있는 모든 열쇠를 순회하면서 방을 방문했는지 확인해야 하기 때문에 추가로 m을 전체 열쇠 개수라고 할 때 O(m)가 필요하다. 따라서 시간 복잡도는 O(n+m)이다. 공간 복잡도는 visited 배열 O(n), dfs 재귀적으로 돌 때 함수가 n번 실행될 수 있으므로 O(n)이라서 O(2n) => O(n)이다.
547. Number of Provinces
n 개의 도시가 있을 때 도시가 직접적으로든 간접적으로 연결되어 있는 경우 1개의 주(province)라고 한다. m x n 크기의 isConnected 배열의 값이 1인 경우 도시는 직접 연결되어있고, 0인 경우는 연결되어있지 않다. 총 주의 개수를 리턴하라.
There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.
A province is a group of directly or indirectly connected cities and no other cities outside of the group.
You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.
Return the total number of provinces.
도시를 노드로 생각하면 isConnected[i][j]는 i 노드와 j 노드가 연결되어 있는지 나타내는 에지라고 할 수 있다. 문제에서 찾는 주의 개수는 한 번에 순회할 수 있는 노드의 덩어리가 몇 개인지 묻는 것으로 생각할 수 있다. 그래서 0번째부터 n-1번째 도시를 순회하면서 그 도시와 직, 간접적으로 연결된 도시를 방문하고, 주 개수를 카운트하면 원하는 답을 찾을 수 있다.
class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
boolean[] visited = new boolean[n];
Queue<Integer> q = new LinkedList<>();
int prov = 0;
for(int i=0; i<n; i++) {
if (!visited[i]) {
visited[i] = true;
prov++;
dfs(isConnected, visited, i, n);
}
}
return prov;
}
private void dfs(int[][] isConnected, boolean[] visited, int i, int len) {
for(int j=0; j<len; j++) {
if (i != j && isConnected[i][j] == 1 && !visited[j]) {
visited[j] = true;
dfs(isConnected, visited, j, len);
}
}
}
}i번째 섬을 방문할 때마다 isConnected[i] 배열의 에지를 모두 확인해야 하기 때문에 시간 복잡도는 O(n^2), 공간복잡도는 visited O(n), dfs를 호출할 때 최악의 경우 함수가 n번 실행될 수 있으므로 O(n)이라서 O(2n) => O(n)이 된다.
