Algorithm

'알고리즘/DFS∕BFS'에 해당되는 글 5건

  1. BOJ 2668 - 숫자고르기
  2. BOJ 1697 - 숨바꼭질
  3. BOJ 1963 - 소수경로
  4. BOJ 4963 - 섬의 개수
  5. BOJ 2178 - 미로 탐색 2

BOJ 2668 - 숫자고르기

알고리즘/DFS∕BFS

문제

https://www.acmicpc.net/problem/2668

풀이

주어진 배열에서 순환하는 요소가 총 몇개인지 카운팅하고, 순환하는 요소들을 오름차순으로 출력하는 문제이다. 아래의 예제 이미지를 보면 순환하는 요소는 1-3, 5 이렇게 3개이다.



정점 N에서 시작하는 순환 배열이 존재하는가를 확인하려면 도착점을 N으로 두고 MAP[N]부터 시작해서 마지막에 N으로 오는가를 확인하면 된다. 만약 N으로 오지 않고 이미 방문했던 정점을 다시 방문한다면 순환 배열이 존재하지 않는다는 뜻이다.

나는 따로 방문을 표시할 배열과 사이클 여부를 표시할 배열을 따로 만들지 않고 방문을 표시할 배열의 값을 0, 1, 2로 구분지어 방문하지 않음, 방문함, 이미 방문했고 사이클이다 라고 정의하여 O(2N)의 공간을 사용하였다.

#include <stdio.h>
int n,map[101]={0},visit[101]={0};
int isCircular(int start, int cur, int count){
	if(visit[cur]) return 0;
	visit[cur] = 1;
	if(start == cur) {
		
		int i;
		for(i=1;i<=n;i++){
			if(visit[i] == 1) visit[i]=2;
		}
		return count+1;
	}
	return isCircular(start,map[cur],count+1);
}
int main(){
	int i,j,ans=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&map[i]);
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(visit[j]==1) visit[j]=0;
		}
		ans += isCircular(i,map[i],0);
	}
	printf("%d\n",ans);
	for(i=1;i<=n;i++){
		if(visit[i]==2)
			printf("%d\n", i);
	}
}


BOJ 1697 - 숨바꼭질

알고리즘/DFS∕BFS

문제

https://www.acmicpc.net/problem/1697

풀이

수빈이가 좌표 N에서 동생이 있는 좌표 K를 찾아가야하는데 수빈이가 동생을 찾는 가장 빠른 시간, 즉 최소 비용을 찾는 문제다. 수빈이는 걷거나 순간 이동을 할 수 있는데 수빈이의 현재 좌표를 X라 할때 X+1, X-1, X*2로 이동할 수 있으며 모든 동작에는 1초의 시간이 걸린다고 한다. 최소 비용을 찾고, 모든 정점의 가중치가 1(초)로 똑같기 때문에 BFS로 해결 할 수 있다. 풀면서 아래의 조건을 체크하여 반복 횟수를 줄였다.

  1. (당연하지만) 한번 방문한 정점은 다시 안가도 된다. 
  2. 최소 비용이 될 수 있는 후보 중 가장 작은 값보다 현재 비용이 크다면 바로 답이 아니라 간주한다.
#include <cstdio>
#include <queue>
using namespace std;
struct movement{
	int x,step;
};
queue<movement> q;
int visit[100001] = {0};
int abs(int x) {return x>0?x:-x;}
int main(){
	int n,k,i,ans;
	movement move;
	
	scanf("%d%d",&n,&k);
	move.x = n;
	move.step = 0;
	
	ans=abs(n-k);

	if(n >= k){
		printf("%d",ans);
		return 0;
	}

	q.push(move);
	while(!q.empty()){
		q.front();
		
		if(q.front().step >= ans){
			q.pop();
			continue;
		}

		if(q.front().x == k) {
			ans = q.front().step;
			q.pop();
			continue;
		}

		move.step = q.front().step + 1;

		if(q.front().x*2 <= 100000 && q.front().x*2 >= 0 && !visit[q.front().x*2]){
			move.x = q.front().x * 2;
			visit[move.x] = 1;
			q.push(move);
		}

		if(q.front().x +1 <= 100000 && !visit[q.front().x+1]) {
			move.x = q.front().x + 1;
			visit[move.x] = 1;
			q.push(move);
		}
		if(q.front().x - 1 >= 0 && !visit[q.front().x-1]){
			move.x = q.front().x - 1;	
			visit[move.x] = 1;
			q.push(move);
		}
		q.pop();
	}
	printf("%d",ans);
}


BOJ 1963 - 소수경로

알고리즘/DFS∕BFS

문제

https://www.acmicpc.net/problem/1963

풀이

나는 가장 먼저 이 문제는 정해진 범위의 소수만을 다루면서 여러 테이스 케이스를 입력받기 때문에 미리 소수를 판별하는 테이블을 만들어 놓았다. 그리고 현재 비밀번호와 현재 비밀번호까지 오는데 몇 번이나 거쳤는지 저장하기 위해 change라는 구조체를 만들어 <queue>에 넣고 1000의 자리부터 1의 자리까지 모두 0~9를 대입하며 큐에 넣고 방문했다는 표시를하여 다시 그 수로 돌아오지 못하게 하여 최소 경로를 찾게 하였다.




#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
struct change{
	int pw,step;
};
int prime[10000]={0};
int main(){
	int t,i,j;
	double sq;
	scanf("%d",&t);
	for(i=1000;i<=9999;i++){
		sq = sqrt((double)i);
		for(j=2;j<=sq;j++){
			if(i%j==0){
				prime[i] = 1;
				break;
			}
		}
	}
	while(t--){
		int visit[10000] = {0};
		queue<change> q;
		change chg;
		int from,dest,digit,rest,ans=987654321;
		scanf("%d%d",&from,&dest);
		chg.pw = from;
		chg.step = 0;
		visit[from] = 1;
		q.push(chg);
		while(!q.empty()){
			if(q.front().step >= ans){
				q.pop();
				continue;
			}
			if(q.front().pw == dest){
				ans = q.front().step;
				q.pop();
				continue;
			}
			for(i=1;i<=1000;i*=10){
				rest = q.front().pw - ((q.front().pw / i) % 10) * i;
				for(j=0;j<=9;j++){
					if(i==1000&&!j) continue;
					if(prime[j*i+rest]||visit[j*i+rest]) continue;
					chg.pw = j*i+rest;
					chg.step = q.front().step + 1;
					q.push(chg);
					visit[chg.pw] = 1;
				}
			}
			q.pop();
		}
		printf("%d\n",ans);
	}
}


BOJ 4963 - 섬의 개수

알고리즘/DFS∕BFS

문제


https://www.acmicpc.net/problem/4963



풀이


기초적인 그래프 탐색 문제이다. 8방향으로 그래프를 탐색해가며 총 컴포넌트(연결되어 있는 노드 집합)의 수를 구해주면 되는데 컴포넌트의 수를 구하기 위해서는 dfs를 몇 번 호출하는지 세어주기만 하면 된다.


방문할 땅과 연결된 모든 땅은 dfs를 통해 방문 표시가 될것이므로 dfs 호출할때 방문하지 않은 땅만 밟으면 총 섬의 개수를 구할 수 있다.



#include<stdio.h>
#include<string.h>
int map[51][51], visit[51][51],w,h;
int dfs(int y,int x){
	int i,j;
	visit[y][x] = 1;
	for(i=-1;i<=1;i++){
		for(j=-1;j<=1;j++){
			if(y+i<1 || x+j<1 || y+i>h || x+j>w) continue;
			if(!visit[y+i][x+j] && map[y+i][x+j])
				dfs(y+i,x+j);
		}
	}
}
int main(){
	while(1){
		int i,j,island=0;
		scanf("%d%d",&w,&h);
		if(!w&&!h) break;
		for(i=1;i<=h;i++){
			memset(map[i],0,sizeof(map[i]));
			memset(visit[i],0,sizeof(visit[i]));
			for(j=1;j<=w;j++)
				scanf("%d",&map[i][j]);
		}
		
		for(i=1;i<=h;i++){
			for(j=1;j<=w;j++){
				if(!visit[i][j] && map[i][j]){
					dfs(i,j);
					island++;
				}
			}
		}
		printf("%d\n",island);
		
	}
}


BOJ 2178 - 미로 탐색

알고리즘/DFS∕BFS

문제




간단한 BFS를 이용한 길 찾기 문제이다. 알고리즘 분류는 BFS로 되어있는데 당연히 DFS로도 된다. 나는 BFS로 구현했다.


소스


#include <iostream>
#include <queue>
using namespace std;

struct pt{
	int x;
	int y;
};

int map[501][101] = {0};
int visit[501][101] = {0};
queue<pt> q;

void setVisit(int x, int y, pt o){
	pt next;
	next.x = x;
	next.y = y;
	q.push(next);
	visit[y][x]+=visit[o.y][o.x]+1;
}
int main(){
	
	int n,m,i,j;char c;
	pt o;
	cin>>n>>m;
	for(i=0;i<n;i++){
		for(j=0;j<m;j++) {
			cin >> c;
			map[i][j]=c-'0';
		}
	}
	o.x=0;o.y=0;
	q.push(o);
	visit[0][0]=1;
	while(!q.empty()){
		pt front = q.front();
		q.pop();
		if(front.x-1 >= 0 && !visit[front.y][front.x-1] && map[front.y][front.x-1])
			setVisit(front.x-1,front.y,front);
		if(front.x+1 < m && !visit[front.y][front.x+1] && map[front.y][front.x+1])
			setVisit(front.x+1,front.y,front);
		if(front.y-1 >= 0 && !visit[front.y-1][front.x] && map[front.y-1][front.x])
			setVisit(front.x,front.y-1,front);
		if(front.y+1 < n && !visit[front.y+1][front.x] && map[front.y+1][front.x])
			setVisit(front.x,front.y+1,front);
	}
	cout << visit[n-1][m-1] << '\n';
}


각 줄마다 띄어쓰기 없이 미로가 주어지므로 char 형으로 받은 다음 '0'(48)을 빼주어 정수형으로 바꾸어주었다.


큐에는 이번에 탐색해야할 좌표 값을 저장해야하므로 x,y값을 가지는 구조체를 만들어 좌표값을 저장시켜 주었고 맨 처음 시작할때 0,0 좌표 변수를 만들어 큐에 넣어주고 시작하게 했다.


탐색을 할때 상하좌우에 이동 할 수 있으며 방문하지 않은곳이 있다면 방문을 했다는 표시를 하고(어차피 큐에 넣고 나중에 방문할것이니 미리 표시해도 상관이 없다) visit[y][x]변수에 몇 번 이도해서 x,y 좌표에 왔는지에 대한 횟수를 적어두게하였다.