547. Number of Provinces
- 한번에 풀지 못했고, intelliJ 를 통해 디버깅을 해야만 했다. 하지만 그렇게 해서라도 해결은 했다.
- 일단 첫번째 문제는, 정사각형 매트릭스에서 대각선은 전부 1 이기 때문에 대각선의 반쪽만 확인하면 될거라고 생각했는데, 맨 위 row 나 i맨 아래 row 같은 경우는, 맨 왼쪽 혹은 맨 오른쪽에서 시작해야만 자신의 connected node 를 가져올 수 있다.
- 그래서 0부터 iteration 을 도는데, visited 정보를 따로 관리 하지 않으면 이게 이미 빠진 건지 아닌지를 알 방법이 없다. 그래서 다시 무한루프에 걸렸었다.
- visited 를 이용하니 해결.
- 성능은 좋지 않다.
- 4ms 였지만, 25%
- 일단 나의 접근은 set 에 전체 노드를 집어 넣어놓고 꺼내면서, 연관된 node 들을 다 꺼내는 priority queue 를 관리하는 것이었다. 그래서 기존의 set 이 empty 가 되면 종료.
- 일단 내 접근에서 문제점은, 쓸데없이 PQ 를 썼다는 것이다. 아무이유 없이. 그냥 Queue 를 썼어도 되었었다.
- 그리고 실제 node 들을 마치 당구공을 주머니에서 꺼내서 다른 주머니에 넣듯이 했는데. HashSet 으로 visit 을 관리할 필요가 전혀 없이, boolean[n] visited 만으로도 충분했다.
- 그래서 처음부터 각 node 를 Set 에 넣을 필요도, visited 를 set 에 넣을 필요도 없었다.
DFS 로도 접근할 수 있는데, 이렇게 접근한 어떤이의 해결법은 다음과 같다. 아래 풀이를 보고 있자면 사실 그렇게 복잡할 필요도 없었겠다는 생각이 든다.
public int findCircleNum(int[][] isConnected) {
boolean[] visited = new boolean[isConnected.length];
int provinces = 0;
for (int i = 0; i < visited.length; i++) {
if (!visited[i]) {
provinces++;
visit(isConnected, i, visited);
}
}
return provinces;
}
private void visit(int[][] isConnected, int origin, boolean[] visited) {
if (!visited[origin]) {
visited[origin] = true;
for (int j = 0; j < isConnected.length; j++) {
if (isConnected[origin][j] == 1) {
visit(isConnected, j, visited);
}
}
}
}
나처럼 BFS 로 접근 한 다른이의 해결법은 아래와 같다.
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
boolean[] visited = new boolean[n];
int count = 0;
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i += 1) {
if (visited[i]) {
continue;
}
count += 1;
queue.add(i);
visited[i] = true;
while (!queue.isEmpty()) {
int current = queue.poll();
for (int j = 0; j < n; j += 1) {
if (j == current || isConnected[current][j] == 0 || visited[j]) {
continue;
}
queue.add(j);
visited[j] = true;
}
}
}
return count;
}
Comments
Post a Comment