SW Expert Academy D4 문제 풀이 (1)

7465. 창용 마을 무리의 개수

N명의 사람에 대해서 두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면 이러한 사람들을 모두 다 묶어서 하나의 무리라고 합니다. 서로를 알고 있는 사람의 관계가 주어질 경우 해당 마을의 무리의 개수를 구하는 문제입니다.

 

이 문제는 각 노드마다 부모 노드를 지정해주고, 같은 부모 노드를 가리키는 노드들은 같은 무리로 지칭하는 유니온 파인드(Union-Find)를 활용하여 문제를 풀었습니다.

 

parent[N+1] 배열의 모든 원소를 자신의 인덱스로 지정해줍니다.

int[] parent = new int[N+1];

for(int i=0;i<N+1;i++){
	parent[i]=i;
}

parent 배열에 각 노드의 부모를 저장해주는 역할을 합니다. 처음에는 각 노드의 부모 노드는 자기 자신이므로 초기값으로 자기 자신을 저장해줍니다.

 

그 다음, union find를 통해 주어진 사람 관계에 해당하는 노드들을 같은 부모를 바라보도록 해줍니다.

static int find(int x){
	if(x!=parent[x]){
		parent[x]=find(parent[x]);
	}
	return parent[x];
}
static void union(int x,int y) {
	int parentX=find(x);
	int parentY=find(y);

	if(parentX!=parentY){
		parent[parentX]=parentY;
	}
}

각 노드가 다른 부모를 가리키고 있다면, 다른 무리에 속한 상태이므로 같은 부모 노드를 가리킬 수 있도록 해줍니다.

각 노드가 같은 부모를 가리키고 있다면, 이미 같은 무리에 속한 상태입니다.

 

초기에 모든 노드는 다른 무리에 속한 상태이므로 무리의 개수는 N입니다. 그러므로 무리의 총 개수를 나타내는 answer의 초기 값은 N입니다.

union 메소드에서 각 노드가 하나의 무리로 합쳐지게 되면 무리의 개수가 1개 줄어들게 됩니다. 그러므로 union 메소드 내부 if문의 조건이 true가 되어 두 노드의 부모 노드가 같아질 경우, answer의 값이 1 줄어들어야 합니다.

그러므로, union에서 if문의 조건이 true일 경우 무리가 하나 줄어들게 되므로 -1을 return하고, if문의 조건이 false일 경우 무리의 개수는 유지되므로 0을 return 해줍니다.

static int union(int x,int y) {
	...
    if(parentX!=parentY){
		...
        return -1;
	}
    return 0;
}

public static void main(String args[]) throws Exception{
	...
	for(int i=0;i<M;i++){
		answer-=union(sc.nextInt(),sc.nextInt());
	}
    ...
}

 

 

4193. 수영대회 결승전 ( 완전 탐색 + 구현 )

삼성이가 바다에서 진행되는 수영 대회에 참여할 때, 장애물을 피해 삼성이가 몇 초만에 도착 지점에 도달할 수 있는지 찾는 문제입니다.

 

이번 문제는 시작 지점에서부터 도착지점으로 가장 빠른 시간으로 도착하는 경로를 구하는 문제로 BFS를 이용해 문제를 풀었습니다.

 

사용된 변수

int N; // 바다의 크기 N*N
int[][] pool; //바다의 형태 0=보통, 1=장애물, 2=소용돌이
boolean[][] visited; // 경로 방문 여부
int A,B; //시작 지점 좌표
int C,D; //종료 지점 좌표

이번 문제에서 많은 실패를 했던 이유는 소용돌이 처리 로직을 제대로 처리하지 못했기 때문입니다.

소용돌이란 문제에서 주어진 장애물 중 하나입니다.

섬의 경우아예 접근할 수 없는 지역이므로 돌아가면 되지만, 소용돌이의 경우 2초 5초 8초에 해당 지역을 넘어갈 수 있으므로, 다른 로직을 세워야 합니다.

 

시도 1. (실패)

첫 번째 시도는 소용돌이가 있는 지점에서의 시간에서 소용돌이를 넘어갈 수 있는 지점으로 이동할 때, 시간을 미리 소용돌이를 건널 수 있는 시간으로 설정한 뒤 바로 Queue에 넣어주도록 했습니다.

이렇게 될 경우, 소용돌이 이후로 이동할 수 있는 구간을 원래 시간보다 느리게 접근 할 수 있게 되어 문제가 되었습니다.

코드를 보고 다시 설명해보도록 하겠습니다.

Queue<Integer> queue; // BFS에 사용할 Queue
while(!queue.isEmpty()){
	int x = queue.poll(), y = queue.poll(); // 현재 지점
    
	int nx, ny; //현재 지점에서 이동할 수 있는 지역(설명을 위해 nx, ny는 0<=nx<N, 0<=ny<N 라고 제한하겠습니다.)
	if(visited[nx][ny] || pool[nx][ny]==1){
		continue;
	}
	
	queue.add(nx);
	queue.add(ny);
	queue.add(time + ((pool[nx][ny]==2) ? 3-(time%3) : 1));
	visited[nx][ny]=true;
}

편의에 의해 생략된 부분이 있으니 양해 부탁드립니다.

 

queue를 이용해 BFS를 구현했고, 다음 탐색할 구간이 아직 방문하지 않았고 산 장애물이 아닐 경우 queue에 넣어줌으로써 계속 탐색할 수 있도록 했습니다.

만약, 소용돌이를 마주했을 경우에는 소용돌이를 이동할 수 있는 시간을 미리 더해줌으로써 해당 지역에 넘어갈 수 있는 시간을 아예 계산하여 넣어줌으로써 빠르게 탐색이 진행될 수 있지 않을까 생각했습니다.

 

하지만, 이렇게 될 경우 문제가 생길 수 있습니다.

그림 1

제가 생각한 로직을 토대로 탐색하게 될 경우의 탐색 순서입니다.

1. (0,0)에서 출발하게 될 경우, 만약 소용돌이(1,0)를 먼저 탐색한다면 queue에는 1(행),0(열),3(시간)이 차례로 넣어질 것입니다.

2. (0,0)의 다음 인접 지점 (0,1)을 탐색한다면 queue에는 0(행),1(열),1(시간)이 차례로 저장될 것입니다.

3. 다음 이동 지역은 queue에 먼저 들어온 (1,0) 좌표 입니다. 해당 좌표에서 (1,1) 지역으로 이동할 수 있게 되므로, (1,1)지역에 이동한 시간은 4가 되고, visited[1][1]이 true가 됩니다.

4. (0,1)에서 (1,1)로 이동하는 시간은 2로 (1,0)에서 (1,1)로 가는 시간인 4보다 빠르지만, 이미 visited[1][1]는 true이므로 (1,1)로 이동할 수 없게 됩니다.

 

제가 생각한 로직대로 움직이게 된다면, 더 빠르게 이동할 수 있는 지역도 느리게 이동하게 될 수도 있기 때문에 실패하게 되었습니다.

 

시도 2. (성공)

이전과 다르게 만약 소용돌이를 마주치게 된다면 현재 좌표를 다시 queue에 넣어주는 방식입니다.

다른 조건들은 동일하게 진행해주고 queue에 넣어주는 로직만 변경해주었습니다.

if(pool[nx][ny]==2 && time%3!=2){
	queue.add(x);queue.add(y);
} else{
	queue.add(nx);queue.add(ny);
	visited[nx][ny]=true;
}
queue.add(time+1);

이동하려는 좌표가 소용돌이이고, 현재 시간이 소용돌이를 지나가지 못하는 시간이라면 queue에 현재 좌표를 넣어줍니다.

다음과 같은 경우 이동하려는 좌표를 queue에 넣어줍니다.

1. 이동하려는 좌표에 장애물이 아무것도 없을 경우

2. 이동하려는 좌표가 소용돌이이지만, 소용돌이를 지나갈 수 있는 시간일 경우

위와 같은 조건일 경우 queue에 이동하려는 좌표를 넣어줍니다.

 

넣어주는 좌표에 상관없이 시간은 1만 흐르게 되므로 time+1을 queue에 넣어줍니다.

 

위와 같이 이동할 경우 어떤 좌표라도 해당 좌표에 도달할 수 있는 가장 빠른 시간에 도착(BFS에 의해)하게 되므로 도착 지점에 도착할 경우의 시간이 답이됩니다.

queue의 원소를 다 소진했음에도(모든 경로를 탐색했음에도) 도착 지점에 도달할 수 없다면, 접근할 수 있는 경로가 존재하지 않다는 의미이므로 답은 -1이 됩니다.

 

 

 

 

6개의 SW Expert Academy의 문제들을 풀게 되었습니다. 원래는 알고리즘 풀이는 파이썬으로 진행해왔지만, 이번에는 자바를 사용게 되었는데 queue나 list와 같은 라이브러리 사용법을 찾아보고 풀이에 적용해야 되서 오래걸리게 되었습니다.

생각보다 풀이를 정리하고 작성하는 시간이 오래걸려 3번 나누어 포스팅을 진행하게 될 것 같습니다. 차근히 다음 포스팅도 올려보도록 하겠습니다.