오늘 할일
1. LeetCode
2. 모바일 프로그래밍 과제
3. 알고리즘 과제
4. 소프트웨어 공학개론 과제
5. 영상처리 Chap7공부
6. 인공지능개론 FAQ 20~
오늘 한일
1. LeetCode
- Number of Provinces는 연결된 도시그룹의 수를 계산하는 문제이다.
/*
일부가 연결되어있는 n개의 도시가 있다.
만약 a와 b, b와 c가 직접적으로 연결되어있다면 a역시 c와 간접적으로 연결된 것으로 간주한다.
Province(주)는 직접적으로, 간접적으로 연결된 그룹을 말하며 그 외 다른 도시들은 그룹에 속하지 않는다.
nxn배열은 연결여부를 나타낸다. isConnected[i][j]==1이라면 i와 j는 직접적으로 연결된 것이다.
전체 주의 개수를 리턴하시오.
*/먼저 가장 쉬운 방법으로 도시 개수n만큼 list를 할당하고, 그룹을 새로이 발견할 때마다 list에 list를 생성하여 연결하는 방법이다. 하지만 최대한 isConnected를 이용해보고싶다.
두번째 방법으로 특정 원소(0~n-1)마다 해당 원소에 연결된 branch들을 재귀적으로 찾아내는 작업을 연결되었다 판단한 원소들을 건너뛰며 수행한 횟수를 계산하는 거것이다.
class Solution {
public int findCircleNum(int[][] isConnected) {
int n=isConnected.length;
int result=0;
int[] is_visited=new int[n];
for(int i=0; i<n; i++){
if(is_visited[i]==0){
result++;
for(int j=0; j<n; j++){
if(isConnected[i][j]==1){
is_visited[j]=1;
}
}
}
}
return result;
}
}
현재 코드는 직접적인 연결만을 고려하기에 1<->3, 2<->3, 2<->3<->4, 1<->3<->4의 예시인 지금 2개로 그룹을 인식하였다.
간접적인 연결을 고려하기 위해 방문처리된 노드의 경우 result++없이 작업을 수행하게 해보았다.
class Solution {
public int findCircleNum(int[][] isConnected) {
int n=isConnected.length;
int result=0;
int[] is_visited=new int[n];
for(int i=0; i<n; i++){//비교원소1
if(is_visited[i]==0){//방문을 안한 비교원소1을 찾았다면
is_visited[i]=1;//방문처리를 하고
result++;//그룹을 새로 추가한다
for(int j=0; j<n; j++)//비교원소2
if(isConnected[i][j]==1)//비교원소 1과 2가 연결되어 있다면
is_visited[j]=1;//j의 방문처리도 수행한다.
} else{//이미 직접적인 방문 처리된 노드라면, result++없이 작업을 수행한다.
for(int j=0; j<n; j++)
if(isConnected[i][j]==1)
is_visited[j]=1;
}
}
return result;
}
}하지만 실패했는데, 관계연결의 순서에 따라 뒤늦게 연결관계가 드러날 수 있기 때문이다.
결국 queue를 사용하여 그룹 별 iteration을 진행하게 하였다. 연관된 모든 city들을 enqueue하여 queue가 빌 때 까지 같은 province로 간주하게 하였다.
class Solution {
public int findCircleNum(int[][] isConnected) {
int n=isConnected.length;
int result=0;
int[] is_visited=new int[n];
for(int i=0; i<n; i++){//비교원소1
if(is_visited[i]==0){//방문을 안한 비교원소1을 찾았다면
is_visited[i]=1;//방문처리를 하고
result++;//그룹을 새로 추가한다
Queue<Integer> queue=new LinkedList<>();
queue.add(i);
while(!queue.isEmpty()){
int city_num=queue.remove();
for(int j=0; j<n; j++) {//비교원소2
if (isConnected[city_num][j] == 1 && j!=i) {//비교원소 1과 2가 연결되어 있다면
if(!queue.contains(j) && is_visited[j]==0)
queue.add(j);
is_visited[j] = 1;//j의 방문처리도 수행한다.
}
}
}
}
}
return result;
}
}
최적화를 위해 queue의 할당대신 clear로 초기화하여 사용하고 불필요한 contains조건을 삭제했다.
class Solution {
public int findCircleNum(int[][] isConnected) {
int n=isConnected.length;
int result=0;
int[] is_visited=new int[n];
Queue<Integer> queue=new LinkedList<>();
for(int i=0; i<n; i++){//비교원소1
if(is_visited[i]==0){//방문을 안한 비교원소1을 찾았다면
is_visited[i]=1;//방문처리를 하고
result++;//그룹을 새로 추가한다
queue.add(i);
while(!queue.isEmpty()){
int city_num=queue.remove();
for(int j=0; j<n; j++) {//비교원소2
if (isConnected[city_num][j] == 1 && j!=i) {//비교원소 1과 2가 연결되어 있다면
if(is_visited[j]==0)
queue.add(j);
is_visited[j] = 1;//j의 방문처리도 수행한다.
}
}
}
}
queue.clear();
}
return result;
}
}
내가 할 수 있는 최대한의 최적화를 2ms인 듯 하여 1ms의 답안을 확인해보았다.
public void dfs(int[][] grid,boolean[] vis,int i){
if(vis[i]){
return;
}
vis[i]=true;
for(int j=0;j<grid[0].length;j++){
if(grid[i][j]==1){
dfs(grid,vis,j);
}
}
}로 visited를 도입한건 같으나, dfs를 활용했다. 종료조건 뿐만아니라 내부적으로 for을 이용해 dfs를 돌리는 아이디어를 나도 숙지하면 좋을 듯 하다. 개인적으로 재귀는 모든 반복문을 사용하지 않아야 한다는 편견이 있는 것 같다.
