<div id="readability-page-1" class="page"><div><h2 id="문제"><a href="#%EB%AC%B8%EC%A0%9C" aria-label="문제 permalink"></a>문제</h2>
지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!
미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.
지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)&nbsp; 이동한다.
불은 각 지점에서 네 방향으로 확산된다.
지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
지훈이와 불은 벽이 있는 공간은 통과하지 못한다.
<h2 id="입력"><a href="#%EC%9E%85%EB%A0%A5" aria-label="입력 permalink"></a>입력</h2>
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.
<ul>
<li><code>#</code> : 벽</li>
<li><code>.</code> : 지나갈 수 있는 공간</li>
<li><code>J</code> : 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)</li>
<li><code>F</code> : 불이 난 공간</li>
</ul>
J는 입력에서 하나만 주어진다.
<h2 id="출력"><a href="#%EC%B6%9C%EB%A0%A5" aria-label="출력 permalink"></a>출력</h2>
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.
<div data-language="cpp"><pre><code>#include &lt;bits/stdc++.h&gt;
using namespace std;

int main()
{
 int r, c;
 cin &gt;&gt; r &gt;&gt; c;
 string str[1002];
 int dx[4] = {0, 0, -1, 1};
 int dy[4] = {1, -1, 0, 0};
 queue&lt;pair&lt;int, int&gt;&gt; exodus;
 queue&lt;pair&lt;int, int&gt;&gt; fire;
 int fDist[1002][1002];
 int jDist[1002][1002];
 for(int i=0;i&lt;r;i++) {
 fill(fDist[i], fDist[i]+c, -1);
 fill(jDist[i], jDist[i]+c, -1);
 }
 for(int i=0;i&lt;r;i++) cin &gt;&gt; str[i];

 for(int i=0;i&lt;r;i++) {
 for(int j=0;j&lt;c;j++){
 if(str[i][j] == 'J') {
 exodus.push({i, j});
 jDist[i][j] = 0;
 }
 if(str[i][j] == 'F') { 
 fire.push({i, j});
 fDist[i][j] = 0;
 }
 }
 }

 while(!fire.empty()) {
 pair&lt;int, int&gt; curF = fire.front();
 fire.pop();
 for(int i=0;i&lt;4;i++) {
 int fx = curF.first + dx[i];
 int fy = curF.second + dy[i];
 // 불 움직이기
 // 1) 불이 가지 못하는 곳
 if(fx &lt; 0 || fx &gt;= r || fy &lt; 0 || fy &gt;=c) continue;
 // 벽이거나 이미 갔던 곳
 if(str[fx][fy] == '#' || fDist[fx][fy] &gt;=0) continue;
 fDist[fx][fy] = fDist[curF.first][curF.second] + 1;
 fire.push({fx, fy});
 }
 }
 while(!exodus.empty()) {
 pair&lt;int, int&gt; curJ = exodus.front();
 exodus.pop(); 
 for(int i=0;i&lt;4;i++) {
 int jx = curJ.first + dx[i];
 int jy = curJ.second + dy[i];
 if(jx &lt; 0 || jx &gt;= r || jy &lt; 0 || jy &gt;=c) {
 cout &lt;&lt; jDist[curJ.first][curJ.second] + 1;
 return 0;
 }
 // 지훈이 움직이기
 // 1) 지훈이가 가지 못하는 곳
 if(str[jx][jy] == '#' || jDist[jx][jy] &gt;= 0) continue;
 // 이미 fire가 다녀간 곳이거나, 도착한 시점에 불이 동시에 도착하거나, 혹은 자신보다 불이 더 빨리 도착하는 자리에 갈 수 없음.
 if(fDist[jx][jy]!=-1 &amp;&amp; fDist[jx][jy] &lt;= jDist[curJ.first][curJ.second]+1) continue;
 jDist[jx][jy] = jDist[curJ.first][curJ.second] + 1;
 exodus.push({jx, jy});
 }
 }
 cout &lt;&lt; "IMPOSSIBLE";
 return 0;
}</code></pre></div></div></div>

Seulog💘

이예슬

문제
지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!
미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.
지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)  이동한다.
불은 각 지점에서 네 방향으로 확산된다.
지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
지훈이와 불은 벽이 있는 공간은 통과하지 못한다.
입력
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.
# : 벽
. : 지나갈 수 있는 공간
J : 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
F : 불이 난 공간
J는 입력에서 하나만 주어진다.
출력
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.
#include <bits/stdc++.h>
using namespace std;
int main()
{
 int r, c;
 cin >> r >> c;
 string str[1002];
 int dx[4] = {0, 0, -1, 1};
 int dy[4] = {1, -1, 0, 0};
 queue<pair<int, int>> exodus;
 queue<pair<int, int>> fire;
 int fDist[1002][1002];
 int jDist[1002][1002];
 for(int i=0;i<r;i++) {
 fill(fDist[i], fDist[i]+c, -1);
 fill(jDist[i], jDist[i]+c, -1);
 }
 for(int i=0;i<r;i++) cin >> str[i];
 for(int i=0;i<r;i++) {
 for(int j=0;j<c;j++){
 if(str[i][j] == 'J') {
 exodus.push({i, j});
 jDist[i][j] = 0;
 }
 if(str[i][j] == 'F') { 
 fire.push({i, j});
 fDist[i][j] = 0;
 }
 }
 }
 while(!fire.empty()) {
 pair<int, int> curF = fire.front();
 fire.pop();
 for(int i=0;i<4;i++) {
 int fx = curF.first + dx[i];
 int fy = curF.second + dy[i];
 // 불 움직이기
 // 1) 불이 가지 못하는 곳
 if(fx < 0 || fx >= r || fy < 0 || fy >=c) continue;
 // 벽이거나 이미 갔던 곳
 if(str[fx][fy] == '#' || fDist[fx][fy] >=0) continue;
 fDist[fx][fy] = fDist[curF.first][curF.second] + 1;
 fire.push({fx, fy});
 }
 }
 while(!exodus.empty()) {
 pair<int, int> curJ = exodus.front();
 exodus.pop(); 
 for(int i=0;i<4;i++) {
 int jx = curJ.first + dx[i];
 int jy = curJ.second + dy[i];
 if(jx < 0 || jx >= r || jy < 0 || jy >=c) {
 cout << jDist[curJ.first][curJ.second] + 1;
 return 0;
 }
 // 지훈이 움직이기
 // 1) 지훈이가 가지 못하는 곳
 if(str[jx][jy] == '#' || jDist[jx][jy] >= 0) continue;
 // 이미 fire가 다녀간 곳이거나, 도착한 시점에 불이 동시에 도착하거나, 혹은 자신보다 불이 더 빨리 도착하는 자리에 갈 수 없음.
 if(fDist[jx][jy]!=-1 && fDist[jx][jy] <= jDist[curJ.first][curJ.second]+1) continue;
 jDist[jx][jy] = jDist[curJ.first][curJ.second] + 1;
 exodus.push({jx, jy});
 }
 }
 cout << "IMPOSSIBLE";
 return 0;
}

[백준]Q4179

댓글