| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 10590 | 2201 | 1245 | 18.898% |
문제
두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.
호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
아래에는 세 가지 예가 있다.
백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.
입력
입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.
다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.
출력
첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.
접근
일반적인 BFS 문제라고 생각했으나, 생각보다 까다로웠다.
1500이란 숫자가 생각보다 커서, 메모이제이션이 굉장히 중요했다.
플로우는 크게 어렵지 않다.
백조의 위치부터 BFS를 시작해 만나는지 확인하고,
만나지 않으면 물과 인접한 얼음들을 지워주고 다음 루프로 간다.
풀이
항상 백조의 위치부터 BFS를 시작하면 TLE가 난다.
그래서 visited를 고정해놓고, 새로 녹는 빙판이 백조가 갈 수 있는 길이면 q에 추가해준다.
다음에 녹을 빙판을 찾는 것도 중요하다.
이번에 녹는 빙판과 인접한 빙판들을 중복되지 않게 next_ice에 넣어줬다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int R, C, ans = 0;
char arr[1500][1500]; // 땅 상태
bool visited[1500][1500], check[1500][1500]; // visited : 백조의 방문 체크, check : 얼음 중복으로 안넣게 체크
vector<pair<int, int>> L, v; // L : 백조(size는 2), v : 이번에 녹을 땅 저장
vector<pair<int, int>> ice, next_ice; // ice :
queue<pair<int, int>> q;
// 범위를 벗어나거나 빙판이면 false return
bool can(pair<int, int> a)
{
int y = a.first, x = a.second;
if (y < 0 || x < 0 || y >= R || x >= C || arr[y][x] == 'X') return false;
return true;
}
bool BFS()
{
while (!q.empty())
{
int y = q.front().first;
int x = q.front().second;
q.pop();
FUP(i, 0, 3)
{
int ny = y + dy[i];
int nx = x + dx[i];
if (!can({ ny, nx }) || visited[ny][nx]) continue;
visited[ny][nx] = true;
q.push({ ny, nx });
}
}
return visited[L[1].first][L[1].second];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
CIN2(R, C);
FUP(i, 0, R - 1)
{
FUP(j, 0, C - 1)
{
visited[i][j] = false;
CIN(arr[i][j]);
if (arr[i][j] == 'L')
{
arr[i][j] = '.';
L.push_back({ i, j });
}
}
}
FUP(i, 0, R - 1)
{
FUP(j, 0, C - 1)
{
if (arr[i][j] != 'X') continue;
check[i][j] = false;
FUP(k, 0, 3)
{
int ny = i + dy[k];
int nx = j + dx[k];
if (can({ ny, nx }))
{
check[i][j] = true;
ice.push_back({ i, j });
break;
}
}
}
}
q.push({ L[0].first, L[0].second });
visited[L[0].first][L[0].second] = true;
while (!BFS())
{
ans++;
next_ice.clear();
for (auto p : ice)
{
arr[p.first][p.second] = '.';
}
for (auto p : ice)
{
FUP(k, 0, 3)
{
int ny = p.first + dy[k];
int nx = p.second + dx[k];
if (ny < 0 || nx < 0 || ny >= R || nx >= C ) continue;
if (arr[ny][nx] == 'X' && !check[ny][nx])
{
check[ny][nx] = true;
next_ice.push_back({ ny, nx });
}
if (visited[ny][nx] && !visited[p.first][p.second])
{
visited[p.first][p.second] = true;
q.push({ p.first, p.second });
}
}
}
ice = next_ice;
}
COUT(ans);
return 0;
}
Beginner