[이코테] 실전 문제

DFS BFS 문제는 dx, dy로 위치 이동을 해가며 stack이나 queue에 넣고빼기를 하면 되는 문제라 다른 문제들보다는 괜찮은 것 같다.

음료수 얼려 먹기

전체 맵에서 아이스크림 개수를 구하는 문제였다. 맵은 0과 1로 이루어져 있고 0이 길(뚫려 있는 부분), 1이 벽(칸막이)이었다. 

 

dx와 dy로 방향을 정하고 dfs 재귀함수에서 4방향 중 한 번도 방문하지 않았고 길이면 다시 dfs로 탐색한다. 이때 아이스크림 개수를 찾는 문제이기 때문에 맵 전체를 탐색해야 한다. for문으로 전체 맵에서 방문하지 않았고 길인 곳에서 dfs 함수를 호출하면 최종적으로 아이스크림 총 개수를 구할 수 있다.

int g[1001][1001];
int N, M;

int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int visit[1001][1001] = { 0 };

void dfs(int x, int y) {
	int i;
	int nx, ny;

	visit[x][y] = 1;	

	for (i = 0; i < 4; i++) { //4방향
		nx = x + dx[i];
		ny = y + dy[i];		
		if (nx >= 0 && nx < N && ny >= 0 && ny < M) {			
			if (visit[nx][ny] == 0 && g[nx][ny]==0) {				
				dfs(nx, ny);
			}
		}
	}
}

int main() {
	int i, j;
	char input[1001];
	int cnt = 0;

	scanf("%d %d", &N, &M);
	
	for (i = 0; i < N; i++) {
		scanf("%s", input);
		for (j = 0; j < M; j++) {
			g[i][j] = input[j] - '0';
		}
	}

	//dfs
	stack<int> s;
	
	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) {
			if (visit[i][j] == 0 && g[i][j] == 0) {
				dfs(i,j);
				cnt++;
			}
		}
	}

	printf("%d", cnt);
}

/*
4 5 
00110
00011
11111
00000
15 14 
00000111100000 
11111101111110 
11011101101110 
11011101100000 
11011111111111 
11011111111100 
11000000011111 
01111111111111 
00000000011111 
01111111111000 
00011111111000 
00000001111000 
11111111110011 
11100011111111 
11100011111111
*/

 

미로 탈출

(1,1)이고 목적지는 (N,M)으로 시작지부터 목적지까지의 최단 거리를 구하는 문제였다. 최단 거리를 구할 때는 bfs를 사용하면 편리하게 풀 수 있다. dfs를 사용하게 된다면 모든 길을 다 탐색해야 하지만 bfs는 목적지에 도달하는 순간 종료할 수 있어 훨씬 효율적이기 때문이다.

 

bfs는 queue를 이용해서 풀 수 있는데 현재 지점에서 4방향 중 방문 가능한 곳을 모두 queue에 넣고 순서대로 pop하면서 반복해주면 된다. 그리고 목적지에 도착하면 즉시 bfs 함수를 종료한다. 목적지의 map 값이 최단 경로가 된다.

 

int N, M;
int map[202][202];
int visit[202][202] = { 0 };

int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

queue<pair<int, int>> q; //좌표 저장

void bfs(int x,int y) {	
	pair<int, int> loc;
	q.push(make_pair(x, y));
	visit[x][y] = 1;

	while (!q.empty()) {
		loc = q.front();
		x = loc.first;
		y = loc.second;
		visit[x][y] = 1;		
		q.pop();
		if (loc.first == N && loc.second == M) return; //출구 도착

		for (int i = 0; i < 4; i++) {
			int nx = loc.first + dx[i];
			int ny = loc.second + dy[i];

			if (nx > 0 && nx <= N && ny > 0 && ny <= M) { //범위 안
				if (map[nx][ny] == 1 && visit[nx][ny] == 0) { //길이고 방문x
					q.push(make_pair(nx, ny));					
					map[nx][ny] = map[x][y]+1;					
				}
			}			
		}
	}
}

int main() {
	char input[201];

	scanf("%d %d", &N, &M);

	for (int i = 1; i <= N; i++) {
		scanf("%s", input);
		for (int j = 1; j <= M; j++) {
			map[i][j] = input[j-1] - '0';
		}
	}

	bfs(1, 1);

	printf("%d", map[N][M]);

}

/*
5 6 
101010 
111111 
000001 
111111 
111111
*/

 

http://www.yes24.com/product/goods/91433923