-
링크 https://www.acmicpc.net/problem/3055
3055번: 탈출
문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나
www.acmicpc.net
접근
물과의 상호작용을 확인 하면서
비버굴로 들어가기 위한 최소 거리 도출
이동조건
고슴도치
영역이내
돌이 아님
물이 차오르지 않을 예정
물
돌이 아님
비버의 소굴이 아님
3차원 배열로 시간 증가에 따른 물의 흐름을 저장한다
깊이가 깊어질 수록 시간과 침범 영역이 증가 한다
탐색을 진행하는 구조체에도 시간을 나타내는 변수를 저장한다
현재 시간의 위치에서 물에 닿지 않고
다음 시간의 위치에서도 물에 닿지 않는다면
탐색을 진행 한다
#include <iostream> #include <queue> #include <vector> #define MAX 51 #define WATER '*' #define ROCK 'X' #define EMPTY '.' #define CHARACTER 'S' #define EXIT 'D' #define DANGER 'R' using namespace std; int dy[4] {-1, 1, 0, 0}; int dx[4] {0, 0, -1, 1}; struct pos{int y, x, t;}; char map[MAX*MAX][MAX][MAX]; int dist[MAX][MAX]; int r, c; void spread(int idx){ int ny, nx; for(int y = 0 ; y < MAX ; y++){ for(int x = 0 ; x < MAX ; x++){ if(map[idx][y][x] != WATER) continue; map[idx+1][y][x] = WATER; for(int i = 0 ; i < 4; i++){ ny = y + dy[i]; nx = x + dx[i]; if(ny < 0 || ny >= r || nx < 0 || nx >= c) continue; if(map[0][ny][nx] == EXIT || map[0][ny][nx] == ROCK) continue; map[idx+1][ny][nx] = WATER; } } } } void spreadAll(){ for(int i = 0 ; i < MAX*MAX -1 ; i++){ spread(i); } } int bfs(pos start, pos end){ int ny, nx; queue<pos> q; dist[start.y][start.x] = 1; q.push(start); while(!q.empty()){ pos s = q.front(); q.pop(); if(s.y == end.y && s.x == end.x){ return dist[s.y][s.x] -1; } for(int i = 0 ; i < 4; i++){ ny = s.y + dy[i]; nx = s.x + dx[i]; if(ny < 0 || ny >= r || nx<0 || nx>=c ) continue; if(map[s.t][ny][nx] == WATER || map[s.t+1][ny][nx] == WATER) continue; if(dist[ny][nx] > 0 || map[0][ny][nx] == ROCK) continue; dist[ny][nx] = dist[s.y][s.x] + 1; q.push({ny, nx, s.t + 1}); } } return -1; } int main(int argc, const char * argv[]) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); pos start, end; cin>>r>>c; for(int y = 0 ; y < r; y++){ for(int x = 0 ; x< c ; x++){ cin>>map[0][y][x]; if(map[0][y][x] == CHARACTER){ start = {y, x, 0}; }else if(map[0][y][x] == EXIT){ end = {y, x, 0}; } } } spreadAll(); int ret = bfs(start, end); if(ret == -1){ cout<<"KAKTUS"<<endl; }else{ cout<<ret<<endl; } return 0; }
'알고리즘 > BFS' 카테고리의 다른 글
백준 2583_영역 구하기 (0) 2020.01.29 12869_뮤탈리스크 (0) 2020.01.28 1963_소수경로 (0) 2020.01.27 [백준 12851] 숨바꼭질 2 (0) 2020.01.01 [백준 9328] 열쇠 (0) 2020.01.01