알고리즘 설명
BFS : 다차원 배열에서 각칸을 방문할 때 너비를 우선으로 방문하는 알고리즘
1.시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
-
큐에서 원소를 꺼내어 그 칸에 상화좌우로 인접한 칸에 대해 3번을 진행
-
해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
-
큐가 빌 때까지 2번을 반복
모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)
Pair : STL에 구현 큐에 좌표를 넣을때 사용
정석적인 BFS를 쓸수있을만큼 반복학습하는게 좋다.
자주 실수 하는 점
-
시작점에 방문했다는 표시를 남기지 않는다.
-
큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문했다는 표시를 남긴다
-
이웃한 원소가 범위를 벗어났는지에 대한 체크를 잘못했다.
- 그림
#include <bits/stdc++.h>
using namespace std;
#define X first;
#define Y second;
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1};
int board[501][501];
bool visited[501][501];
int n, m;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
int cnt = 0, ians = 0;
for (int i = 0; i < n; i++)
{
for (int k = 0; k < m; k++)
{
cin >> board[i][k];
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (board[i][j] == 1 && visited[i][j] == 0)
{
cnt++;
int iMax = 0;
queue <pair<int, int>> q;
q.push({ i,j });
visited[i][j] = 1;
while (!q.empty())
{
int cx = q.front().X;
int cy = q.front().Y;
q.pop();
iMax++;
for (int dir = 0; dir < 4; dir++)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
if (board[nx][ny] == 0 || visited[nx][ny] == 1) continue;
visited[nx][ny] = 1;
q.push({ nx,ny });
}
}
ians = max(ians, iMax);
}
}
}
cout << cnt << '\n' << ians << '\n';
}BFS의 정석적인 틀을 사용해볼수있는 Flood Fill 기초 문제였다 BFS의 시작점을 발견 하였을때 카운트를 증가시켜 그림의 갯수를 세고 BFS를 탐색하는동안 그림의 크기를 재기위한 변수 iMax를 만들어 1씩 증가시킨다 BFS탐색이 끝나고 난뒤 iAns에 저장된 맥스값과 비교를 통해 큰값을 넣어주면 된다.
2178 . 미로 탐색
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
int board[101][101];
int dis[101][101];
int n, m;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
string str;
cin >> str;
for (int j = 0; j < str.size(); j++)
{
board[i][j] = str[j] - '0';
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (board[i][j] == 1 && dis[i][j] == 0)
{
queue <pair<int,int> > q;
q.push({ i,j });
while (!q.empty())
{
pair <int, int> cur = q.front();
q.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (board[nx][ny] == 0 || dis[nx][ny] != 0) continue;
dis[nx][ny] = dis[cur.X][cur.Y] + 1;
q.push({ nx, ny });
}
}
}
}
}
cout << dis[n - 1][m - 1] + 1 << '\n';
}
최단 거리 탐색을 연습해볼수있는 문제였다 Flood Fill과는 다르게 visited가아닌 dis에 거리를 저장하고 거리가 0인경우에만 BFS로 탐색할수있게 설정했다.
7576 토마토
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
int board[1001][1001];
int n, m;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> m >> n;
int cnt = 0;
queue <pair<int,int>> q;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> board[i][j];
if (board[i][j] == 1)
{
q.push({ i,j });
}
}
}
while (!q.empty())
{
pair <int, int> cur = q.front();
q.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (board[nx][ny] == -1 || board[nx][ny] > 0) continue;
board[nx][ny] = board[cur.X][cur.Y] + 1;
q.push({ nx,ny });
}
}
int imax = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (board[i][j] == 0)
{
cout << -1 << '\n';
return 0 ;
}
else if (board[i][j] != -1)
{
imax = max(imax, board[i][j]);
}
}
}
cout << imax - 1 << '\n';
return 0;
}
여러개의 시작점이 있는 BFS를 활용하는 문제였다 보드에 입력을 받을때 토마토가있는칸에 큐에 입력해준다 이렇게하면 여러개의 시작점으로부터 BFS를 돌릴수있다 다음 큐가 빌때까지 bfs를 돌린후(nm을벗어나거나 토마토가없는칸 이미 방문한칸(값이 0보다 큰경우) 는 방문하지않는다) 보드를 차례대로 탐색하며 0인칸이있다면 -1를 출력해주고 아니라면 최대값을 구해준뒤 1을 빼주면 정답을 구할수있다.
7569 . 토마토
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = { 0,0,1,0,-1,0 };
int dy[] = { 0,0,0,1,0,-1 };
int dz[] = { 1,-1,0,0,0,0 };
int board[101][101][101];
int visited[1001][1001];
int n, m, h;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> m >> n >> h;
int cnt = 0;
queue <tuple<int,int,int>> q;
for (int k = 0; k < h; k++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> board[k][i][j];
if (board[k][i][j] == 1)
{
q.push({k, i,j });
}
}
}
}
while (!q.empty())
{
tuple <int,int, int> cur = q.front();
q.pop();
for (int dir = 0; dir < 6; dir++)
{
int nz = get<0>(cur) + dz[dir];
int nx = get<1>(cur) + dx[dir];
int ny = get<2>(cur) + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || nz < 0 || nz >= h) continue;
if (board[nz][nx][ny] == -1 || board[nz][nx][ny] > 0) continue;
board[nz][nx][ny] = board[get<0>(cur)][get<1>(cur)][get<2>(cur)] + 1;
q.push({nz, nx,ny });
}
}
int imax = 0;
for (int k = 0; k < h; k++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (board[k][i][j] == 0)
{
cout << -1 << '\n';
return 0;
}
else if (board[k][i][j] != -1)
{
imax = max(imax, board[k][i][j]);
}
}
}
}
cout << imax - 1 << '\n';
return 0;
}
위문제에서 2차원이 3차원으로 변경된것이다.
우선 배열들을 3차원으로 선언해주고 기존의 4방향에 위와 아래를 추가해준다
int dx[] = { 0,0,1,0,-1,0 };
int dy[] = { 0,0,0,1,0,-1 };
int dz[] = { 1,-1,0,0,0,0 };
다음 pair는 두개의 정수를 보관할수있으므로 3개의 정수를 보관하기위해 tuple 자료형을 사용한다 tuple은 get<0> ( cur) 를 통해 정수를 가져올수있다.
4179 불
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = {1,0,-1,0 };
int dy[] = {0,1,0,-1 };
int board[1001][1001];
int visited[1001][1001];
int fireboard[1001][1001];
int r, c;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> r >> c;
queue <pair<int, int>> jh;
queue <pair<int, int>> fire;
for (int i = 0; i < r; i++)
{
string str;
cin >> str;
for (int j = 0; j < str.size(); j++)
{
if (str[j] == '#')
board[i][j] = -1;
else if (str[j] == 'F')
{
fireboard[i][j] = 1;
fire.push({ i, j });
}
else if (str[j] == 'J')
{
board[i][j] = 1;
jh.push({ i,j });
}
}
}
while (!fire.empty())
{
auto cur = fire.front();
fire.pop();
for (int i = 0; i < 4; i++)
{
int nx = cur.X + dx[i];
int ny = cur.Y + dy[i];
if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
if (fireboard[nx][ny] >= 1 || board[nx][ny] == -1) continue;
fireboard[nx][ny] = fireboard[cur.X][cur.Y] + 1;
fire.push({nx, ny});
}
}
while (!jh.empty())
{
auto cur = jh.front();
jh.pop();
for (int i = 0; i < 4; i++)
{
int nx = cur.X + dx[i];
int ny = cur.Y + dy[i];
if (nx < 0 || nx >= r || ny < 0 || ny >= c)
{
cout << board[cur.X][cur.Y] << '\n';
return 0;
}
if ((fireboard[nx][ny] != 0 && fireboard[nx][ny] <= board[cur.X][cur.Y] + 1 ) || board[nx][ny] == -1 || board[nx][ny] >= 1) continue;
board[nx][ny] = board[cur.X][cur.Y] + 1;
jh.push({ nx, ny });
}
}
cout << "IMPOSSIBLE\n";
}
두개의 큐를 이용해 BFS를 돌려 해결해여한다 하나는 불을 하나는 지훈이가 길을 이어나가는 큐이다 우선 fire큐 를 BFS를 통해 불이 번질수있는 지역마다 그지역에 불이 붙기까지 얼마의 시간이 걸리는지 BFS를 통해 구한다 다음 지훈이가 갈수있는 지역을 BFS를통해 구할때 기존의 조건에 지훈이가 도착한 시간 보다 불이 번지는 시간이 적은지 검사해야한다 같은경우는 가자마자 불이붙기때문에 갈수없는 지역이다 또한 (fireboard[nx][ny] != 0 && fireboard[nx][ny] <= board[cur.X][cur.Y] + 1 ) 이부분이 중요한데 fireboard[nx][ny] != 0를 넣어주는 이유는 불이 꼭 모든 공간에 붙으리라는 보장이 없기때문이다 예를들어 3 4
###F
.J#.
###. 의 경우 J의 옆 공간은 불이 붙지 못한다 하지만 저 조건을 넣어주지않을경우 불이 붙지않았지만 fireboard에 0으로 표기되어있고 벽이아니기때문에 지훈이가 갈수없다고 판단한다. 이를 예외처리해주기위해선 저 조건이 필요하다.
if (nx < 0 || nx >= r || ny < 0 || ny >= c)
{
cout << board[cur.X][cur.Y] << '\n';
return 0;
}
그리고 외곽으로 나갔을경우엔 탈출에 성공했으므로 그 시간을 출력해주면된다 만약 큐가 다비워졌음에도 탈출하지 못했다면 탈출 불가이므로 임파서블을 출력해준다.
1697 . 숨바꼭질
#include <bits/stdc++.h>
using namespace std;
int arr[200002];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
if (n == k)
{
cout << 0 << '\n';
return 0;
}
queue <int> q;
q.push(n);
while (!q.empty())
{
int cur = q.front();
q.pop();
for (int nxt : {cur - 1, cur + 1, cur * 2})
{
if (nxt < 0 || nxt >= 200002) continue;
if (arr[nxt] != 0) continue;
arr[nxt] = arr[cur] + 1;
if (nxt == k)
{
cout << arr[nxt] << '\n';
return 0;
}
q.push(nxt);
}
}
return 0;
}기존의 bfs와는 달리 1차원에서 해결해야하는 bfs였다 우선 n과 k를 입력받은뒤 같다면 0을출력하고 종료한다.
보드의 역할을 하는 arr배열의 크기는 200002로 잡았는데 그 이유는 k는 10만아래지만 n은 그보다 더 나아간다음 줄어들수도있다 하지만 이는 매우 비효율적인 일이기때문에 10만보다 커질일은 거의 없을것이고 문제에서 공간에 제약이 넓기때문에 넉넉하게 20만을 잡아주었다.
다음으로는 n을 큐에 집어넣고 범위기반 for문을통해 -1 +1 *2를 돌리면 만약 nxt가 k와같다면 인자를 출력해주고 종료한다.
1012 . 유기농 배추
#include <bits/stdc++.h>
using namespace std;
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int cnt;
cin >> cnt;
while (cnt--)
{
int board[52][52]{};
bool visited[52][52]{};
int n, m , k ,ans = 0;
cin >> m >> n >> k ;
for (int i = 0; i < 52; i++)
{
fill(board[i], board[i] + 52, 0);
fill(visited[i], visited[i] + 52, 0);
}
for (int i = 0; i < k; i++)
{
int x, y;
cin >> x >> y;
board[y][x] = 1;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (board[i][j] == 1 && visited[i][j] == 0)
{
queue <pair<int, int>> q;
q.push({ i, j });
visited[i][j] = 1;
ans++;
while (!q.empty())
{
int cx = q.front().first;
int cy = q.front().second;
q.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (board[nx][ny] == 0 || visited[nx][ny] == 1) continue;
visited[nx][ny] = 1;
q.push({ nx,ny });
}
}
}
}
}
cout << ans << '\n';
}
}기초적인 BFS를 통한 방문 문제이다 가로 세로 좌표값이 기존문제와 다르니 잘 확인해야한다.
2583 . 영역 구하기
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
int board[101][101];
bool visited[101][101];
int n, m,k;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> m >> n >> k;
priority_queue<int,vector<int>,greater <int>> pq;
for (int i = 0; i < k; i++)
{
int x1, x2, y1, y2;
cin >> x1 >> y1 >> x2 >> y2;
for (int i = y1; i < y2; i++)
{
for (int j = x1; j < x2; j++)
{
board[i][j] = 1;
}
}
}
int ans = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (board[i][j] == 0 && visited[i][j] == 0)
{
visited[i][j] = 1;
ans++;
int area=0;
queue <pair<int, int>> q;
q.push({ i,j });
while (!q.empty())
{
int cx = q.front().X;
int cy = q.front().Y;
q.pop();
area++;
for (int dir = 0; dir < 4; dir++)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if (board[nx][ny] == 1 || visited[nx][ny] == 1) continue;
visited[nx][ny] = 1;
q.push({ nx,ny });
}
}
pq.push(area);
}
}
}
cout << ans << '\n';
while (!pq.empty())
{
cout << pq.top() << ' ';
pq.pop();
}
}2차원 BFS문제이다 문제에서 사각형의 꼭짓점이 반대로 주어지기 때문에 이를 수정해야줘야할것같지만 그렇지않아도된다 상하가 반전된 모습이겠지만 어차피 넓이를 구하는 문제이니 이는 중요하지않다.
for문을 통해 점 2개를 입력받고 점2개에해당하는 구역의 board 를 1로 해준다 다음 0인칸을 bfs를통해 큐에 처음들어가는 수가 갯수고 pop해주며 더해주는 넓이를 구해 우선순위큐에 넣어 정렬후 출력해주면된다.
2667 . 단지 번호 붙이기
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
int board[26][26];
bool visited[26][26];
int n;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
int ans = 0;
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < n; i++)
{
string str;
cin >> str;
for (int j = 0; j < n; j++)
{
board[i][j] = str[j] - '0';
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (board[i][j] == 1 && visited[i][j] == 0)
{
ans++;
visited[i][j] = 1;
queue <pair<int, int>> q;
q.push({ i,j });
int area = 0;
while (!q.empty())
{
auto cur = q.front();
q.pop();
area++;
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (board[nx][ny] == 0 || visited[nx][ny] == 1) continue;
visited[nx][ny] = 1;
q.push({ nx,ny });
}
}
pq.push(area);
}
}
}
cout << ans << '\n';
while (!pq.empty())
{
cout << pq.top() << '\n';
pq.pop();
}
}특별한 점이 없는 bfs문제이다 전 문제에서 활용한 바와같이 우선순위큐를 이용하여 넓이를 저장하고 출력해준다.
7562 . 나이트의 이동
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = { -2,-2,-1,-1,1,1,2,2};
int dy[] = { +1,-1,+2,-2,+2,-2,1,-1};
int board[302][302];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int cnt = 0;
cin >> cnt;
while (cnt--)
{
int n;
for (int i = 0; i < 302; i++)
{
fill(board[i], board[i] + 302, -1);
}
cin >> n;
int cNX, cNY, nNX, nNY;
cin >> cNX >> cNY >> nNX >> nNY;
board[cNX][cNY] = 0;
queue < pair<int, int>> q;
q.push({ cNX,cNY });
bool clear = 0;
if (cNX == nNX && cNY == nNY)
{
cout << 0 << '\n';
clear = 1;
}
while (!q.empty() && !clear)
{
auto cur = q.front();
q.pop();
for (int dir = 0; dir < 8; dir++)
{
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (board[nx][ny] != -1) continue;
if (nx == nNX && ny == nNY)
{
cout << board[cur.X][cur.Y] + 1 << '\n';
clear = 1;
break;
}
board[nx][ny] = board[cur.X][cur.Y] + 1;
q.push({ nx,ny });
}
}
}
}체크 보드에서 나이트의 이동 문제이다 우선 dx,dy를 기존의 4방향이아닌 나이트가 갈수있는 8개 칸의 좌표로 바꾼다 다음은 cnt를 전칸보다 1씩 더해가며 BFS돌리면서 만약 도착칸이라면 출력해주면된다.
10026 . 적록색약
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
string board[102];
bool visited[102][102];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> board[i];
}
int ans1 = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (visited[i][j] == 0)
{
queue <pair<int, int>> q;
char pick = board[i][j];
visited[i][j] = 1;
q.push({ i,j });
ans1++;
while (!q.empty())
{
int cx = q.front().X;
int cy = q.front().Y;
q.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (visited[nx][ny] == 1 || board[nx][ny] != pick) continue;
visited[nx][ny] = 1;
q.push({ nx,ny });
}
}
}
}
}
for (int i = 0; i < 101; i++)
{
fill(visited[i], visited[i] + 101, 0);
}
int ans2 = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (visited[i][j] == 0)
{
queue <pair<int, int>> q;
char pick = board[i][j];
visited[i][j] = 1;
q.push({ i,j });
ans2++;
while (!q.empty())
{
int cx = q.front().X;
int cy = q.front().Y;
q.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (visited[nx][ny] == 1) continue;
if (pick == 'R' || pick == 'G')
{
if(board[nx][ny] == 'B')
continue;
}
else
{
if (board[nx][ny] != 'B')
continue;
}
visited[nx][ny] = 1;
q.push({ nx,ny });
}
}
}
}
}
cout << ans1 << ' ' <<ans2 << '\n';
}기본적인 BFS문제에서 0과1이아닌 세가지로 변수가있고 한번은 R과G가 다른값을 한번은 같은 값을 가지도록 하는문제이다
우선 string형식의 크기를 101 + 1로 선언하고 입력을 받는다 처음엔 rgb를 따로 잡아야 하므로 처음 bfs를 시작하는 기준의 char를 pick에 저장해 다르다면 continue하게 하고 다음엔 r과 g를 같은 형식으로 보게해서 bfs돌리면 정답을 구할수있다.
9466 . 텀 프로젝트
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int want[100002];
bool visited[100002];
bool done[100002];
int ans = 0;
void DFS(int nodenum)
{
visited[nodenum] = 1;
int next = want[nodenum];
if (!visited[next])
DFS(next);
else if (!done[next])
{
for (int i = next; i != nodenum; i = want[i])
{
ans++;
}
ans++;
}
done[nodenum] = 1;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int cnt = 0;
cin >> cnt;
while (cnt--)
{
fill(want, want + 100002, 0);
fill(visited, visited + 100002, 0);
fill(done, done + 100002, 0);
ans = 0;
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> want[i];
}
for (int i = 1; i <= n; i++)
{
if (!visited[i])
DFS(i);
}
cout << n - ans << '\n';
}
}DFS를 통해 문제를 해결한다 want 배열엔 원하는 사람을 입력하고 visited는 이 칸을 방문했는지 done은 이 칸이 사이클을마무리했느지를 표시한 배열이다.
우선 want 배열을 입력받은뒤 반복문을 통해 1부터 N까지 아직방문하지않은 칸에 대해 DFS 함수를 호출한다
DFS함수는 우선 인자 nodenum에 해당하는 visit을 1로 만들어 방문했음을 표시하고 want[nodenum]을 next에 저장한다.
다음 next가 아직 방문되지않았다면 DFS(next)를 통해 빠진다.
만약 DFS함수중에 방문한칸을 만났을때 해당칸이 방문은 했지만 아직 done되지않았다면 해당 DFS내에서 사이클이 이루어진경우이다 그런경우 else if 문 안으로 들어가 현재 next값부터 자신까지 넘어가며 싸이클의 노드수를 ans에 더한다 다음 맨 마지막에 호출된 DFS부터 자신에 해당하는 done칸의 값을 1로 바꿀것이다.
이렇게 모든칸을 방문하고 나면 ans에 싸이클에 포함되는 노드수가 저장되어있으니 총 노드수에서 해당 수를 빼주면 정답을 구할수있다.
2206 . 벽부수고 이동하기
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int board[1002][1002];
int visited[1002][1002][2];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
string str;
cin >> str;
for (int j = 0; j < m; j++)
{
board[i][j] = str[j] - '0';
}
}
queue<pair<pair<int, int>, int>> q;
visited[0][0][1] = 1;
q.push({ { 0,0}, 1 });
while (!q.empty())
{
int cx = q.front().X.X;
int cy = q.front().X.Y;
int broke = q.front().Y;
q.pop();
if (cx == n - 1 && cy == m - 1)
{
cout << visited[cx][cy][broke] << '\n';
return 0;
}
for (int dir = 0; dir < 4; dir++)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (board[nx][ny] == 1 && broke == 1)
{
visited[nx][ny][0] = visited[cx][cy][1] + 1;
q.push({ { nx,ny}, 0 });
}
else if (board[nx][ny] == 0 && visited[nx][ny][broke] == 0)
{
visited[nx][ny][broke] = visited[cx][cy][broke] + 1;
q.push({ { nx,ny}, broke });
}
}
}
cout << -1 << '\n';
}기존의 BFS를 통한 길찾기에 벽을 부술수있는 기회가 1회 추가된 유형이다.
우선 거리를 표시할 visit배열을 3차원으로 기존의 배열을 2중으로 선언해준다. 그이유는 벽을 부셨을때와 안부셨을때를 각각 표시해야하기 떄문이다 이는 큐에서도 똑같이 적용해 기존의 pair에 벽을 부셨는지를 기록할 broke를 추가해준다
우선 처음 스타트 0,0에 아직벽을 부시지않았음으로 1을 visit배열에 표시하고 q에넣어준다
다음 기존 bfs와 동일하게 진행하는데 큐에서 인자를 꺼낼때 x,y와더불어 broke까지 꺼낸다 여기서 만약 좌표가 탈출지점이라라면 해당값을 출력하고 종료한다.
다음은 bfs로 들어가는데 여기서 nx,ny가 범위에 들어오는 지확인하고 두가지의 경우로 나뉜다
- 갈칸이 벽이고 아직벽을 부시지 않은경우
이때는 벽을 무조건 부수고 가고 visit[nx][ny][0]에 기입하고 큐에넣어준다
여기서 else문을 걸면 3가지의 경우가 더있다
- 갈칸이 벽이고 벽을 이미 부신경우 3.갈칸이 벽이아니고 능력을 씀에따라 하나더 4.
2번은 큐에 넣어줄필요가없으니 3.4는 else if문을 통해 조건을 걸어준다 벽이 아닌것과 갈칸이 아직 방문하지않았음이 조건이다. 다음은 위와 동일하게 visited배열에 표시하고 큐에 넣어주면된다.
이렇게 함으로써 칸을 진행하면서 벽을만날때마다 해당벽을 부수고 간경우와 부수지 않고 간경우가 모두 저장될것이고 모든 경우의수를 확인할수있을것이다.
2468 안전영역
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int board[102][102];
int visited[102][102];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int H_max = 0;
int H_min = 101;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> board[i][j];
H_max = max(H_max, board[i][j]);
H_min = min(H_min, board[i][j]);
}
}
int irain = H_min-1;
int ans = 0;
while (irain <= H_max)
{
int water = 0;
memset(visited, 0, sizeof(visited));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (board[i][j] > irain && visited[i][j] == 0)
{
visited[i][j] = 1;
water++;
queue <pair<int, int>> q;
q.push({ i,j });
while (!q.empty())
{
int cx = q.front().X;
int cy = q.front().Y;
q.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (board[nx][ny] <= irain || visited[nx][ny] == 1) continue;
visited[nx][ny] = 1;
q.push({ nx,ny });
}
}
}
}
}
ans = max(water, ans);
irain++;
}
cout << ans << '\n';
}방문하는 기준을 늘려가면서 BFS를 구현하는 문제이다.
우선 입력값을 배열에 저장하며 최소값과 최대값을 구한다 BFS를 1부터 100까지 돌려도되지만 최소값과 최대값을 안다면 그 범위 내에서만 놀리면 시간을 절약할수있기때문이다.
다음 내린비의 양 irain을 최소값-1로잡고 (아무것도 잠기지않는 부분부터 시작 ) 최대값과 같을때가지 1씩더해주며 BFS를돌린다 water에 bfs에 큐에 처음들어가는 값의 갯수를 저장하고 ans와 max연산을 통해 최대값을 기록해주면 정답을 구할수있다.
2573 . 빙산
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int board[302][302];
int visited[302][302];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> board[i][j];
}
}
int ans = 0;
while (1)
{
int snow= 0;
memset(visited, 0, sizeof(visited));
queue <pair<int, int>> q2;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (board[i][j] > 0 && visited[i][j] == 0)
{
visited[i][j] = 1;
snow++;
queue <pair<int, int>> q;
q.push({ i,j });
q2.push({ i,j });
while (!q.empty())
{
int cx = q.front().X;
int cy = q.front().Y;
q.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (board[nx][ny] == 0 || visited[nx][ny] == 1) continue;
visited[nx][ny] = 1;
q.push({ nx,ny });
q2.push({ nx,ny });
}
}
}
}
}
if (snow >= 2)
{
cout << ans << '\n';
return 0;
}
if (snow == 0)
{
cout << "0\n";
return 0;
}
int board2[302][302]{};
memcpy(board2, board, sizeof(board));
while (!q2.empty())
{
int x = q2.front().X;
int y = q2.front().Y;
q2.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (board[nx][ny] > 0) continue;
if (board2[x][y] > 0)
(board2[x][y])--;
}
}
memcpy(board, board2, sizeof(board));
ans++;
}
}우선 board에 값을 입력받는다 다음 기본적인 bfs로 빙산의 갯수를 센다 여기서 큐하나를 더만들어서(q2) 빙산 즉값이 있는 칸들을 넣어준다 이렇게 큐에 미리 값을 넣어두면 빙산을 녹일때 반복문을 또돌려서 빙산을 찾을 시간을절약할수있다.
그리고 빙산의 갯수를 샌뒤 만약 빙산의 갯수가 2보다크다면 지난 햇수 cnt를 출력하고 종료하고 0이라면 0을 출력하고 종료한다.
조건을 만족하지못했다면 빙산을 녹여야한다 여기서 직관적으로 보드에서 바로 빙산을 녹이면 오차가발생한다
만약에 빙산을 녹여서 물이되면 오른쪽 빙산을 녹일때 왼쪽빙산과 같이 녹아야하나 왼쪽을 물로 보기 때문이다 떄문에 보드를 하나더 만들어 카피를 한후 보드 1을 기준으로 2을 녹여주고 2를 1에 복사해주어야한다
여기서 큐에 넣은 좌표값을 들을 기준으로 빙산을 녹여주면 된다.
5247 . 불
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int board[1002][1002];
int fireboard[1002][1002];
int visited[1002][1002];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int cnt = 0;
cin >> cnt;
while (cnt--)
{
int n, m;
cin >> m >> n;
memset(fireboard, -1, sizeof(fireboard));
memset(visited, 0, sizeof(visited));
queue <pair<int, int>> sq;
queue <pair<int, int>> fq;
for (int i = 0; i < n; i++)
{
string str;
cin >> str;
for (int j = 0; j < str.size(); j++)
{
if (str[j] == '#')
{
board[i][j] = -2;
}
else if (str[j] == '@')
{
board[i][j] = 0;
sq.push({ i,j });
}
else if (str[j] == '*')
{
board[i][j] = -2;
fireboard[i][j] = 0;
fq.push({ i,j });
}
else if (str[j] == '.')
{
board[i][j] = -1;
}
}
}
while (!fq.empty())
{
int cx = fq.front().X;
int cy = fq.front().Y;
fq.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (board[nx][ny] == -2 || fireboard[nx][ny] >= 0) continue;
fireboard[nx][ny] = fireboard[cx][cy] + 1;
fq.push({ nx,ny });
}
}
while (!sq.empty())
{
int cx = sq.front().X;
int cy = sq.front().Y;
sq.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m)
{
cout << board[cx][cy] + 1 << '\n';
goto NEXT;
}
if (board[nx][ny] == -2 || board[nx][ny] >= 0 || (fireboard[nx][ny] != -1 && (fireboard[nx][ny] <= board[cx][cy] + 1))) continue;
board[nx][ny] = board[cx][cy] + 1;
sq.push({ nx,ny });
}
}
cout << "IMPOSSIBLE\n";
continue;
NEXT:
continue;
}
}이전에 풀었던 불!문제와 같은 문제이다 복습을 하는차원에서 다시 풀어봤다. 테스트케이스만 추가되었을뿐 달라진점은 없다.
2146 다리만들기
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int board[102][102];
int check[102][102];
int dist[102][102];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> board[i][j];
}
}
int ans = 100000;
int landcnt = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (board[i][j] == 1 && check[i][j] == 0)
{
queue < pair<int, int>> landq;
check[i][j] = ++landcnt;
landq.push({ i,j });
while (!landq.empty())
{
int cx = landq.front().X;
int cy = landq.front().Y;
landq.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (board[nx][ny] == 0 || check[nx][ny] > 0) continue;
check[nx][ny] = check[cx][cy];
landq.push({ nx,ny });
}
}
}
}
}
for (int k = 1; k <= landcnt; k++)
{
queue <pair<int, int>> q;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
dist[i][j] = -1;
if (check[i][j] == k)
{
dist[i][j] = 0;
q.push({ i,j });
}
}
}
while (!q.empty())
{
int cx = q.front().X;
int cy = q.front().Y;
q.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if ( dist[nx][ny] != -1) continue;
dist[nx][ny] = dist[cx][cy] + 1;
q.push({ nx,ny });
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (check[i][j] != 0 && check[i][j] != k)
{
ans = min(dist[i][j],ans);
}
}
}
}
cout << ans -1 << '\n';
}우선 BFS를 통해 각섬에 번호를 달아주어야한다. 그래야 각섬으로부터의 거리를 잰후 다른섬의 경우만 거리를 파악할수있기때문이다.
기본적인 BFS에서 flood fill과 같지만 값을 landcnt로 처음 발견된 섬부터 1씩증가하면서 넣어준다.
이렇게하면 board에는 섬에경우 1 바다 0 check 에는 각섬의 인덱스가 붙어있을것이다.
다음으로는 기존의 2중for문의 가장 바깥에 k로 landcnt까지의 반복을 해준다 각섬마다 bfs를 통해 섬외곽 부터 전체 맵의 거리를 잰후 맵을 탐색하여 현재 섬이아니고 다른섬의 dist를 재어 최소값을 구해 ans에 넣어준다
마지막을 정답 ans를 출력할땐 다리의 길이이므로 1을 빼고 출력해주면 정답을 구할수 있다.
13549 . 숨바꼭질 3
#include <bits/stdc++.h>
using namespace std;
int board[100002];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
fill(board, board + 100002, -1);
board[n] = 0;
deque <int> q;
q.push_back(n);
while (!q.empty())
{
int cx = q.front();
q.pop_front();
if (cx == k)
{
cout << board[cx] << '\n';
return 0;
}
for (int i = 0; i < 3; i++)
{
int nx = 0;
switch (i)
{
case 0:
nx = cx * 2;
break;
case 1:
nx = cx + 1;
break;
case 2:
nx = cx - 1;
break;
default:
break;
}
if (nx < 0 || nx > 100000) continue;
if (board[nx] >= 0) continue;
switch (i)
{
case 0:
board[nx] = board[cx];
q.push_front(nx);
break;
case 1:
case 2:
board[nx] = board[cx] + 1;
q.push_back(nx);
break;
default:
break;
}
}
}
}기존 1차원 bfs문제의 변형이다 1초를 소비하여 +1 -1칸을 이동하는것에서 0초를 소비하여 *2칸을 이동하는것이 추가되었다 그렇다면 기존의 풀이에서 이부분을 추가해주면될것이다.
기존의 1초를 이동할때 큐에 뒤쪽에 넣어주었으니 순간이동은 어떻게 처리해줘야할까?
정답은 큐의 앞에 넣어주는것이다 기존의 이동은 큐에 뒤에넣어주었으니 순차적으로 처리되었고 순간이동은 큐의 앞에넣어주어 바로바로 진행되고 시간값또한 늘어나지않게 해준다면 이를 구현할수있다.
큐는 PUSH_BACK만을 지원하기때문에 덱으로 이를 구현해 순간이동은 푸쉬 프론트로 해준다 (나머지 이동은 전과 같다)
그리고 순간이동으로 이동할때는 보드의 시간값을 증가시키지않는다 K칸에 도달하면 해당하는 보드값을 출력하고 종료한다.
13913 . 숨바꼭질 4
#include <bits/stdc++.h>
using namespace std;
int board[100010];
int parent[100010];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
fill(board, board + 100010, -1);
fill(parent, parent + 100010, -1);
board[n] = 0;
queue<int> q;
q.push(n);
while (!q.empty())
{
int cx = q.front();
q.pop();
if (cx == k)
{
cout << board[cx] << '\n';
int temp = k;
stack<int> s;
while (1)
{
s.push(temp);
if (temp == n)
break;
temp = parent[temp];
}
while (!s.empty())
{
cout << s.top() << ' ';
s.pop();
}
return 0;
}
for (int i = 0; i < 3; i++)
{
int nx = 0;
switch (i)
{
case 0:
nx = cx - 1;
break;
case 1:
nx = cx + 1;
break;
case 2:
nx = cx * 2;
break;
}
if (nx < 0 || nx >= 100010) continue;
if (board[nx] >= 0) continue;
board[nx] = board[cx] + 1;
parent[nx] = cx;
q.push(nx);
}
}
}기존 숨바꼭질 문제와 같은 1차원 bfs이다 하지만 정답을 출력할때 그 과정을 출력해야한다.
정답을 구하는 과정은 기존과 같으나 정답을 구하면서 그 숫자에 도달한 부모를 기록해야한다.
우선 보드와 같은 크기의 parent배열을 선언한다 다음 board[nx] = board[cx] + 1; 다음
parent[nx] = cx; 를통해 부모배열에 해당 nx의 전값을 넣어준다.
다음 cx = k 정답을 발견하면 board값을 출력한후 반복문을통해 마지막값부터 스택에 넣어주고 temp = parent[temp] 를 통해 값을 역추적하여 넣어준후 스택이 빌때 까지 출력해주면 정답을 올바르게 구할수있다
1600 . 말이 되고픈 원숭이
#include <bits/stdc++.h>
using namespace std;
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
int dx2[] = { -2,-2,-1,-1,1,1,2,2 };
int dy2[] = { 1,-1,2,-2,2,-2,1,-1 };
int board[202][202];
bool visited[202][202][31];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int w, h , k;
cin >> k >> w >> h;
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
cin >> board[i][j];
}
}
queue <pair<pair< int, int>, pair<int, int >>> q;
q.push({ {0,0},{0,0} });
visited[0][0][0] = 1;
while (!q.empty())
{
int cx = q.front().first.first;
int cy = q.front().first.second;
int cnt = q.front().second.first;
int jump = q.front().second.second;
q.pop();
if (cx == h - 1 && cy == w - 1)
{
cout << cnt << '\n';
return 0;
}
if (jump < k)
{
for (int dir = 0; dir < 8; dir++)
{
int nx = cx + dx2[dir];
int ny = cy + dy2[dir];
if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
if (board[nx][ny] == 1 || visited[nx][ny][jump + 1] != 0) continue;
visited[nx][ny][jump + 1] = 1;
q.push({ {nx,ny},{cnt + 1,jump + 1} });
}
}
for (int dir = 0; dir < 4; dir++)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
if (board[nx][ny] == 1 || visited[nx][ny][jump] != 0) continue;
visited[nx][ny][jump] = 1;
q.push({ {nx,ny},{cnt+1,jump} });
}
}
cout << "-1\n";
}2차원 bfs문제에 k번 점프를 할수있는 조건이 붙은 문제이다. 기존의 점프문제 처럼 visited배열을 선언한다 여기서 k의 최대값인 30만큼 3차원으로 선언한다.
큐는 4개의 int값을 가지게 선언한다. 1,2번값 x,y축 좌표를 의미하고 3번째는 cnt 이동한 횟수 ,4번째는 점프를 사용한 횟수를 기록하기 위해사용한다.
다음은 일반적인 bfs와 동일하다. 다른점은 jump < k 즉, 아직 점프를 사용할수있는 횟수가남은경우 기존의 이동과 더불어 dx2,dy2를 이용해 점프를 사용한다 이때 큐에 넣을때 cnt값과 더불어 jump값도 1증가시켜 넣어준다.
3197 . 백조의 호수
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
bool visited[1501][1501];
string str[1501];
vector<pair<int, int>> target;
queue<pair<int, int>> water;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int r, c;
cin >> r >> c;
for (int i = 0; i < r; i++)
{
cin >> str[i];
for (int j = 0; j < c; j++)
{
if (str[i][j] == 'L')
{
target.push_back({ i,j });
str[i][j] = '.';
water.push({ i,j });
}
else if (str[i][j] == '.')
{
water.push({ i,j });
}
}
}
queue<pair<int, int>> q;
visited[target[0].X][target[0].Y];
q.push({ target[0].X,target[0].Y });
int cnt = 0;
while (1)
{
queue <pair<int, int>> next;
while (!q.empty())
{
int cx = q.front().X;
int cy = q.front().Y;
q.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || ny < 0 || nx >= r || ny >= c || visited[nx][ny]) continue;
if (target[1] == make_pair(nx, ny))
{
cout << cnt << '\n';
return 0;
}
else if (str[nx][ny] == 'X')
{
next.push({ nx,ny });
}
else q.push({ nx,ny });
visited[nx][ny] = 1;
}
}
q = next;
cnt++;
int n = water.size();
while (n--)
{
int cx = water.front().X;
int cy = water.front().Y;
water.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || nx >= r || ny < 0 || ny >= c)continue;
if (str[nx][ny] == 'X')
{
str[nx][ny] = '.';
water.push({ nx, ny });
}
}
}
}
}보드의 크기가 1500 * 1500이기때문에 시간제한을 피하기위한 여러 부분을 사용해야한다.
visited 배열과 board는 각각 기존의 방문 체크와 보드 역할을 하고
타켓 벡터는 백조의 위치를 저장 water는 물의 좌표를 저장한다.
물의 좌표를 넣어놓은 이유는
매번 얼음을 녹일때마다 반복문을통해 얼음을 녹이는것이 아닌 미리 물의 좌표를 넣어놓고 얼음을녹이고 녹은 얼음의 좌표를 다시 물에 넣어 보드를 갱신하기 위함이다.
다음은 r과 c 를입력받아 보드에 넣는다 이때 L즉 백조가 들어오면 타겟 벡터에 넣어주고 그칸은 물이기 때문에 .로 바꿔주고 water큐에 넣어준다 .또한 water큐에 넣어준다.
다음은 타겟의 0 즉 먼저들어온 백조부터 bfs를 시작한다 bfs를 돌면 타겟 1을 만날경우 cnt를 출력하고 종료하고 아닐경우 우선 얼음을만났는지 검사한다. bfs를통해 만날얼음은 이번 녹는점에 녹기때문에 (물과닿아있다) next 큐에 넣어 q.empty 반복문이 끝나면 q = next를 통해 넥스트큐를 q큐에넣어준다. 벽이 아닌경우는 물이기때문에 q에 넣어 계속해서 bfs에넣어주고 두경우 모두 방문한것이기 때문에 visited배열에 체크해준다.
만약 여기서 다른 백조에 방문하지 못했다면 물에 인접한 얼음을 녹여주어야한다.
water배열엔 이번에 녹음얼음 즉 다음에 4면을 녹일물을 넣을것이기때문에 water.empty로 검사하는것이 아닌 water.size로 워터 큐의 크기를 미리 구해 그만큼 반복문을 돌려준다.
다음은 여타 bfs와 같이 4방면을 검사해 얼음이있다면 녹이고 water큐에 넣어준다.
반복문은 다음으로 넘어가고 q에는 전반복에서 마주친 얼음부터 반복문을 시작할것이다.
11967 . 불켜기
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
int visited[102][102];
vector<pair<int, int>> light[102][102];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, x, y, a, b;
cin >> n >> m;
while (m--)
{
cin >> x >> y >> a >> b;
light[x][y].push_back({ a,b });
}
visited[1][1] = 2;
queue<pair<int, int>> q;
q.push({ 1,1 });
int cnt = 1;
while (!q.empty())
{
int cx = q.front().X;
int cy = q.front().Y;
q.pop();
for (auto p : light[cx][cy])
{
int tx = p.first;
int ty = p.second;
if (visited[tx][ty] != 0)continue;
visited[tx][ty] = 1;
for (int dir = 0; dir < 4; dir++)
{
int nx = tx + dx[dir];
int ny = ty + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (visited[nx][ny] == 2)
{
visited[tx][ty] = 2;
q.push({ tx,ty });
}
}
cnt++;
}
for (int dir = 0; dir < 4; dir++)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (visited[nx][ny] == 1)
{
q.push({ nx,ny });
visited[nx][ny] = 2;
}
}
}
cout << cnt << '\n';
}지금까지의 방식과는 다르게 생각을 요하는 문제이다.
우선 방의 상태를 저장할 visted배열을 선언한다 상태는 0,1,2로
0 : 불이꺼져있고 방문하지않은 방
1 : 불은 켰으나 아직 방문하지않은 방
2 : 불도 켰고 방문한 방
3가지로 나뉜다.
다음은 각 방의 스위치를 저장할 light벡터이다 각 벡터행렬의 벡터는 그 방이 가지고있는 스위치를 의미한다.
다음 n,m,a,b를 입력받아 배열과 벡터를 채워주고
1,1부터 bfs를 시작한다 cnt는 켜진 방의 불수를 의미한다 1,1 방문했기때문에 cnt는 1부터 시작한다 다음 q큐에는 방문해서 그방의 스위치를 켤차례인 방을 저장한 큐를 의미한다.
다음 반복문을 통해 q를 순서대로 꺼내면서 우선 그방의 스위치를 범위기반for문을 통해 탐색한다
만약 먼저 스위치를 키기전에 그방의 상태가 0이아니라면 이미 탐사한경우이기떄문에 continue로 넘어가준다.
우선 방의 상태를 불을 킨상태로 1로 변경해준다.
다음 일단 스위치를 켠방의 4방면을 검사해 방의상태가 2인경우가있는지 검사한다. 매 반복문을 돌릴떄마다 모든 보드를 확인하는것이아닌 그때그때 해당하는 방을 탐색하는식으로 문제를 해결해야 시간초과를 면할수있다.
다음 그방의 불을 킨것이기 때문에 cnt를 1늘려준다
다음은 현재 방문한 방의 4방면을 검사해 만약 방문상태가 1인경우 2로바꾸고 큐에 넣어준다.
bfs가 끝나면 cnt를통해 불이 켜진 방수를 구할수있다.
17071 . 숨바꼭질 5
#include <bits/stdc++.h>
using namespace std;
int board[2][500001];
int sum(int n)
{
return n * (n + 1) / 2;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
queue<pair<int, int>> q;
q.push({ n,0 });
memset(board, -1, sizeof(board));
while (!q.empty())
{
int cx = q.front().first;
int time = q.front().second;
q.pop();
if (cx < 0 || cx > 500000 || board[time % 2][cx] != -1) continue;
board[time % 2][cx] = time;
q.push({ cx - 1,time + 1 });
q.push({ cx + 1,time + 1 });
q.push({ 2 * cx,time + 1 });
}
for (int i = 0; i < 500000; i++)
{
int kcnt = k + sum(i);
if (kcnt > 500000)
break;
if (board[i % 2][kcnt] != -1 && board[i % 2][kcnt] <= i)
{
cout << i << '\n';
return 0;
}
}
cout << -1 << '\n';
}기존의 숨바꼭질에서 동생이 이동하는것이 추가되었다. 여기서 동생이 이동하는게 하는것은 어렵지않으나 수빈이가 그칸에 딱맞는걸 계산하는것은 쉽지않다. 그렇기 때문에 한가지 혜안이 필요하다.
바로 만약 수빈이가 먼저 동생이 갈칸에 도착해있고 그때의 시간값의 %2 값이 같다면 수빈이가 왼쪽 오른쪽으로 이동하며 그칸에 머무르면 동생을 만날수있다는것이다.
이를 구현하기위해 board를 [2][500001]으로 선언해준다. 먼저 수빈이를 bfs를통해 board에 행은 time %2로 해서 인자는 time으로 넣어준다.
다음은 동생을 이동시킨다 sum함수를 통해 값을 누적시켜 더해줘서 kcnt가 50만보다 커질때까지 진행하며 조건 (board[i % 2][kcnt] != -1 && board[i % 2][kcnt] <= i)를 통해 kcnt값이 -1아니고 작다면 수빈이가 그칸에서 기다릴수있으니 i를 출력해준다 만약 반복문을 탈출한경우는 수빈이와 동생이 만나지 못하는 경우이다.
16920 . 확장게임
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int cnt[9];
int dist[9];
string board[1002];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, p;
cin >> n >> m >> p;
for (int i = 0; i < p; i++)
{
cin >> dist[i];
}
queue<pair<int, int>> q[9];
for (int i = 0; i < n; i++)
{
cin >> board[i];
for (int j = 0; j < m; j++)
{
if (board[i][j] >= '1' && board[i][j] <= '9')
{
q[board[i][j] - '1'].push({ i,j });
cnt[board[i][j] - '1']++;
}
}
}
while (1)
{
bool flag = false;
for (int i = 0; i < p; i++)
{
int len = dist[i];
while (!q[i].empty() && len--)
{
int size = q[i].size();
for (int castle = 0; castle < size; castle++)
{
int cx = q[i].front().X;
int cy = q[i].front().Y;
q[i].pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (board[nx][ny] == '.')
{
board[nx][ny] = '1' + i;
q[i].push({ nx,ny });
cnt[i]++;
flag = true;
}
}
}
}
}
if (!flag)
break;
}
for (int i = 0; i < p; i++)
{
cout << cnt[i] << ' ';
}
}각 플레이어마다 이동할수있느 칸수의 제한이있고 그칸수만큼 성을 확장해 보드가 꽉찼을때 각 플레이어의 성의 갯수를 구하는 문제이다.
먼저 플레이어의 성의갯수를 저장할 cnt배열,플레이어별 이동칸수를 저장할 dist배열과 보드가 필요하다.
다음으로 nmp를 입력받아 저장하주고 p만큼 이동칸수를 dist에 입력받는다 다음 board에 입력을 저장하며 숫자가들어온경우 q에 넣어주고 해당하는 숫자의 플레이어의 cnt를 1늘려준다(성갯수 증가)
다음으로는 반복문을 통해 보드가 꽉찰때까지 bfs를 활용해 성을 확장한다.
우선 bool변수 flag가 필요하다 초기값은 false가진다 .에 성이 건설될때 true가되고 만약 한번 플레이어가 모두 돌았을때 flag가 false라면 더이상 확장이 불가능한것이고 반복문을 탈출한다.
다음은 반복문을 통해 0부터 p까지 반복문을 돌린다(플레이어 1부터 성을 확장)
각 플레이어는 큐가 비었거나 (더이상 갈칸이없음) len이 0이될떄가지(보유한 이동횟수를 모두 사용함) while문을 통해 bfs를 돈다.
한번 이동할때마다 size를통해 해주지않으면 추가된 성에서 또 바로이동을 해버리므로 size를통해 현재 큐의 크기를 저장해 그만큼 bfs를 돌려준다 (현재 큐에있는 즉 현재 플레이어가 보유하고있는 성만 확장을함 확장을통해 얻은 성의 확장은 len--를 하고나서)
'.' 비어있는 땅을만난경우 플레이어에 해당하는 숫자로 변경해주고 큐에삽입 cnt를 1늘려준다.
반복문을 탈출할때까지 돌리면 cnt에 각플레이어의 성의갯수를 출력해주면 정답을 구할수있다.
