일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
- 불량 사용자
- 티스토리
- Open API
- 카카오 인턴
- 가사 검색
- bulk update
- jdbc
- pycon
- 징검다리 건너기
- 알고리즘
- 트라이 #trie #알고리즘
- Python
- 크레인 인형뽑기 게임
- 트라이
- Spring Boot
- 보행자 천국
- 튜플
- CleanCode
- 프로그래머스
- trie
- 티스토리 open api
- 호텔 방 배정
- Tistory
- Today
- Total
택시짱의 개발 노트
[백준] 5427번 불 본문
링크
https://www.acmicpc.net/problem/5427
5427번: 불
문제 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다. 빌딩
www.acmicpc.net
풀이
빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 문제이다.
문제를 보았을 때 탈출구에 상근이가 먼저 도착하면 되겠다 라는 생각을 했다.
탈출할 수 있다면 빠른 시간에 탈출해야 되기 때문에 BFS를 이용했는데
상근이랑 불이 어떤 위치에 최소 시간에 도달할 수 있는지를 확인하여 서로 비교하기 위해서
상근이 2차원 배열과 불 2차원 배열을 각각 2개 만들어 BFS를 이용하여
각각의 위치에 최소 시간에 도달할 수 있는 시간을 구하였다.
이때 X , Y 위치의 상근이와 불의 시간을 비교하였을 때 상근이가 불의 시간보다 빠르다면 그 위치는 갈 수 있는 곳이 된다.
조건 (상근이가 방문 했고 && (불이 방문하지 않거나 || 상근이가 불보다 먼저 도착할때))
이용하여 탈출구가 될 수 있는 건물의 모서리 부분을 모두 탐색하여
결괏값을 찾을 수 있었다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>
#define SIZE 1010
const int INF = 2000000000;
using namespace std;
typedef long long int ll;
char arr[SIZE][SIZE];
int man_v[SIZE][SIZE];
int fire_v[SIZE][SIZE];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
typedef struct Loc {
int x, y;
bool what;
}Loc;
void init() {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
man_v[i][j] = -1;
fire_v[i][j] = -1;
}
}
}
queue<Loc> q;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int T; cin >> T;
while (T--) {
init();
int N, M; cin >> M >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> arr[i][j];
if (arr[i][j] == '@') {
Loc m; m.x = i; m.y = j; m.what = true;
q.push(m); man_v[i][j] = 0;
}
else if (arr[i][j] == '*') {
Loc f; f.x = i; f.y = j; f.what = false;
q.push(f); fire_v[i][j] = 0;
}
}
}
while (!q.empty()) {
Loc h = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
Loc n; n.x =h.x+ dx[d]; n.y = h.y + dy[d]; n.what = h.what;
if (n.x < 0 || n.x >= N || n.y < 0 || n.y >= M || arr[n.x][n.y] == '#')
continue;
if (h.what == true) {//man
if (man_v[n.x][n.y] != -1)
continue;
else if (man_v[n.x][n.y] == -1) {
man_v[n.x][n.y] = man_v[h.x][h.y] + 1;
q.push(n);
}
}
else if (h.what == false) {//fire
if (fire_v[n.x][n.y] != -1)
continue;
else if (fire_v[n.x][n.y] == -1) {
fire_v[n.x][n.y] = fire_v[h.x][h.y] + 1;
q.push(n);
}
}
}
}
int res = INF;
for (int i = 0; i < N; i++) {
if ((man_v[i][0] < fire_v[i][0] || fire_v[i][0] == -1) && man_v[i][0] != -1) {
res = min(res, man_v[i][0]);
}
if ((man_v[i][M - 1] < fire_v[i][M - 1] || fire_v[i][M-1] == -1)&& man_v[i][M - 1] != -1) {
res = min(res,man_v[i][M-1]);
}
}
for (int j = 0; j < M; j++) {
if ((man_v[0][j] < fire_v[0][j] || fire_v[0][j] == -1) && man_v[0][j] != -1) {
res = min(res, man_v[0][j]);
}
if ((man_v[N-1][j] < fire_v[N-1][j] || fire_v[N-1][j] == -1) && man_v[N-1][j] != -1) {
res = min(res, man_v[N-1][j]);
}
}
if (res == INF)
cout << "IMPOSSIBLE\n";
else
cout << res +1 << "\n";
}
}
'알고리즘' 카테고리의 다른 글
[프로그래머스] 튜플 (0) | 2020.04.01 |
---|---|
[프로그래머스] 크레인 인형뽑기 게임 (0) | 2020.04.01 |
[백준] 17127번 벚꽃이 정보섬에 피어난 이유 (0) | 2020.03.31 |
[백준] 13913번 숨바꼭질 4 (0) | 2020.03.30 |
[백준] 12851번 숨바꼭질 2 (0) | 2020.03.30 |