오늘의 키워드
어제 오늘 프로그래머스에서 코테 문제를 10개 풀었는데, 그 중에 절반이 BFS 문제였던 것 같다.
원래 BFS/DFS 둘 다 사용해도 되는 문제가 나오면 DFS를 사용하는걸 더 선호했는데, 어제 오늘 BFS만 계속 해서 그런지 이제 BFS가 더 쉬운것 같다.
BFS (Breadth-First Search, 너비우선탐색)
BFS와 DFS
BFS는 DFS와 같이 트리나 그래프를 순회하는 대표적인 방법 중 하나이다. 참고로 DFS는 Depth-First Search로 우리말로는 깊이우선탐색이라고 한다. 아래의 이미지는 두 알고리즘의 동작 방식을 이해하기 쉽게 보여준다.
DFS는 갈림길을 만나면 갈림길의 위치를 기억해뒀다가, 막다른 길이 나올 때까지 직진하고, 막다른 길이 나오면 마지막 갈림길 위치로 되돌아와서 가지 않은 갈림길 쪽으로 간다.
BFS는 갈림길을 만나면 갈 수 있는 가까운 곳부터 넓게 넓게 퍼져나가는 식으로 탐색한다.
따라서, DFS는 마지막 갈림길의 위치를 기억하기 위해 stack이나 재귀함수를 이용해 구현하고, BFS는 현재 방문 가능한 모든 노드들을 순차적으로 방문하기 위해 queue를 이용해 구현한다.
BFS의 특징
BFS로 방문되는 모든 노드들은 시작노드로부터 최단거리를 보장해준다. (단, 간선에 가중치가 없다는 가정)MST(최소 신장 트리)를 구하는Prim알고리즘과 유사하다.- 최단경로를 구하는
Dijkstra알고리즘과 유사하다.
왜 Queue를 씀?
BFS와 queue는 뗄 수 없는 관계다. BFS 구현의 핵심은 방문 할 수 있는 가장 가까운 노드부터 순서대로 방문한다 인데, 이 말은 곧 방문 할 수 있는 노드들을 싹 다 queue에 넣어놓고, 꺼내면서 방문하기만 하면 된다는 것이다. 왜냐하면 queue는 FIFO(선입선출) 자료구조이기 떄문.
대략적인 구현
queue<int> q;
while (!q.empty()) //queue가 비어있지 않으면 계속 반복
{
int node = q.front(); //이번에 방문한 node
q.pop();
cout << node << " ";
for (auto e : graph) //방문 가능한 node 탐색
{
if (e[0] == node && !visited[e[1]]) //이번 node와 연결돼 있고, 아직 방문하지 않은 node라면,
{
visited[e[1]] = true; //방문했다고 기록하고 queue에 push
q.push(e[1]);
}
}
}여기서 visited 배열은 node들을 방문한 적이 있는지 기록하기 위해 사용하는데, 방문한 node들을 기록하지 않는다면 이미 방문한 곳을 왔다갔다하게 되면 무한루프에 빠지게 돼서 그렇다.
프로그래머스 - 리코쳇 로봇 (Lv.2)
문제 설명
리코쳇 로봇이라는 보드게임이 있습니다.
이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.
이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.
다음은 보드게임판을 나타낸 예시입니다.
...D..R .D.G... ....D.D D....D. ..D....여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.게임판의 상태를 나타내는 문자열 배열
board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.제한 사항
- 3 ≤ board의 길이 ≤ 100
- 3 ≤ board의 원소의 길이 ≤ 100
- board의 원소의 길이는 모두 동일합니다.
- 문자열은 ".", "D", "R", "G"로만 구성되어 있으며 각각 빈 공간, 장애물, 로봇의 처음 위치, 목표 지점을 나타냅니다.
- "R"과 "G"는 한 번씩 등장합니다.
입출력 예
board result ["...D..R", ".D.G...", "....D.D", "D....D.", "..D...."]7 [".D.R", "....", ".G..", "...D"]-1
해결방안
기본적인 BFS문제라고 생각한다. 대신에 이 문제는 방문 가능한 노드를 판단하는 방법만 기본에서 살짝 비틀었는데, 바로 로봇이 미끄러지면서 이동한다는 것이다. 벽이나 맵의 바깥에 부딛히기 전엔 멈출 수도 없고, 방향을 틀 수도 없다.
또, 착각하면 안되는 점이 있는데, 그건 미끄러지는 동안 거쳐가는 노드들은 방문한 것이 아니라는 것이다. 따라서, 미끄러지는 동안 목표지점을 지나쳐도 탐색을 종료하면 안된다. 딱 어딘가에 부딛혀서 멈춘 곳만 방문한 곳이 되는거다. 이것은 calPos라는 함수를 따로 작성하여 처리했다.
#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
vector<int> calPos(int dir, int x, int y, vector<string>& board)
{
vector<int> dx = { 1, -1, 0, 0 };
vector<int> dy = { 0, 0, 1, -1 };
while (0 <= x && x < board.size() && 0 <= y && y < board[0].size())
{
if (board[x][y] == 'D')
break;
else
{
x += dx[dir];
y += dy[dir];
}
}
x -= dx[dir];
y -= dy[dir];
return { x, y };
}
int solution(vector<string> board)
{
vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
queue<vector<int>> q;
vector<int> startPos, goalPos;
for (int i = 0; i < board.size(); i++)
{
for (int j = 0; j < board[0].size(); j++)
{
if (board[i][j] == 'R')
startPos = { i, j };
if (board[i][j] == 'G')
goalPos = { i, j };
}
}
q.push({startPos[0], startPos[1], 0});
visited[startPos[0]][startPos[1]] = true;
while (!q.empty())
{
auto n = q.front();
q.pop();
if (n[0] == goalPos[0] && n[1] == goalPos[1])
return n[2];
for (int i = 0; i < 4; i++)
{
auto nextPos = calPos(i, n[0], n[1], board);
if (0 <= nextPos[0] && nextPos[0] < board.size() && 0 <= nextPos[1] && nextPos[1] < board[0].size())
{
if (!visited[nextPos[0]][nextPos[1]])
{
visited[nextPos[0]][nextPos[1]] = true;
q.push({ nextPos[0], nextPos[1], n[2] + 1 });
}
}
}
}
return -1;
}프로그래머스 - 미로 탈출 (Lv.2)
문제 설명
1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.
미로를 나타낸 문자열 배열
maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.제한 사항
- 5 ≤ maps의 길이 ≤ 100
- 5 ≤ maps[i]의 길이 ≤ 100
- maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
- S : 시작 지점
- E : 출구
- L : 레버- O : 통로- X : 벽
- 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
- 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.
입출력 예
maps result ["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]16 ["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"]-1
해결방안
입출력 예 1번의 맵을 그려보면 이렇게 생겼다. 우리는 START에서 시작해서 중간에 LEVER가 있는 곳을 거친 뒤, EXIT까지 가는 최단 거리를 찾아야한다.
여기서 생각해야 할 점은..
1. LEVER를 켰다면, 이미 왔던 길을 돌아서 가야 EXIT로 가는 최단거리가 나올 수도 있다.
2. 현재 방문한 node에 여태까지 이동한 거리를 함께 저장한다.
1번의 경우는 BFS 내부에서 조건문으로 걸러내려먼 머리가 되게 아파지는데, 생각보다 간단한 방법으로 해결 가능하다. 바로 START -> LEVER로 가는 BFS를 한번, LEVER -> EXIT로 가는 BFS 한번, 이렇게 두번 수행하면 끝이다.
2번의 경우에는 q에 삽입하는 데이터를 { positionX, positionY, distance } 이렇게 저장할 생각이다.
#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
int BFS(vector<int> startPos, vector<int> goalPos, vector<string>& maps)
{
queue<vector<int>> q;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
vector<vector<bool>> visited(maps.size(), vector<bool>(maps[0].size(), false));
q.push({ startPos[0], startPos[1], 0 });
visited[startPos[0]][startPos[1]] = true;
while (!q.empty())
{
auto n = q.front();
q.pop();
if (n[0] == goalPos[0] && n[1] == goalPos[1])
return n[2];
for (int i = 0; i < 4; i++)
{
int nextX = n[0] + dx[i];
int nextY = n[1] + dy[i];
if (0 <= nextX && nextX < maps.size() && 0 <= nextY && nextY < maps[0].size())
{
if (!visited[nextX][nextY] && maps[nextX][nextY] != 'X')
{
visited[nextX][nextY] = true;
q.push({ nextX, nextY, n[2] + 1 });
}
}
}
}
return -1;
}
int solution(vector<string> maps)
{
vector<int> startPos;
vector<int> leverPos;
vector<int> goalPos;
for (int i = 0; i < maps.size(); i++)
{
for (int j = 0; j < maps[0].size(); j++)
{
if (maps[i][j] == 'S')
startPos = { i, j };
if (maps[i][j] == 'L')
leverPos = { i, j };
if (maps[i][j] == 'E')
goalPos = { i, j };
}
}
int cnt1 = BFS(startPos, leverPos, maps);
if (cnt1 == -1) return -1;
int cnt2 = BFS(leverPos, goalPos, maps);
if (cnt2 == -1) return -1;
return cnt1 + cnt2;
}프로그래머스 - 무인도 여행 (Lv.2)
문제 설명
메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.
지도를 나타내는 문자열 배열
maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.제한사항
- 3 ≤ maps의 길이 ≤ 100
- 3 ≤ maps[i]의 길이 ≤ 100
- maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
- 지도는 직사각형 형태입니다.
입출력 예
maps result ["X591X","X1X5X","X231X","1XXX1"][1, 1, 27]["XXX","XXX","XXX"][-1]
해결방안
입출력 예 1번의 맵을 그려보면 위의 이미지와 같다.
먼저, 섬을 어떻게 구분해야할지 고민해야하는데, for문과 BFS로 해결 가능하다. 맵의 한 칸 한 칸 for문으로 탐색하며, 바다가 아닌 칸이 나오면 그 칸에서 BFS를 시작한다. 그러면 그 칸이 속해 있는 섬 전체를 탐색하게 되고, BFS가 끝나면 다시 for문으로 돌아와서 다음 섬을 찾을 수 있다.
단, 위에서 풀었던 미로 탈출 문제는 BFS를 여러번 수행 할 때 visited도 같이 초기화 했던 반면에 이 문제는 그렇게 해선 안된다. for문 단계에서도 visited 배열의 상태를 공유해야 같은 섬을 또 탐색하는 일이 벌어지지 않기 때문이다.
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cctype>
#include <iostream>
using namespace std;
vector<int> solution(vector<string> maps)
{
vector<int> answer;
int h = maps.size();
int w = maps[0].size();
vector<vector<bool>> visited(h, vector<bool>(w, false));
queue<pair<int, int>> q;
vector<pair<int, int>> movement = { {0, -1}, {0, 1}, {1, 0}, {-1, 0} };
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
if (isalpha(maps[i][j]))
visited[i][j] = true;
}
}
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
if (!visited[i][j])
{
q.push({ i, j });
visited[i][j] = true;
int islandSum = 0;
while (!q.empty())
{
auto e = q.front();
islandSum += maps[e.first][e.second] - '0';
q.pop();
for (int i = 0; i < 4; i++)
{
int x = e.first + movement[i].first;
int y = e.second + movement[i].second;
if ((0 <= x && x < h) && (0 <= y && y < w))
{
if (!visited[x][y])
{
q.push({ x, y });
visited[x][y] = true;
}
}
}
}
answer.push_back(islandSum);
}
}
}
if (answer.size() == 0)
answer.push_back(-1);
else
sort(answer.begin(), answer.end());
return answer;
}마치며
알고리즘에서 BFS는 정말 강력한 무기이다. 최단 거리를 찾을 때도 좋고, 중복 없이 tree나 graph, 혹은 지도와 같은 형태를 띄는 배열을 탐색할 때도 좋다.
게다가, prim, dijkstra와 같은 알고리즘과도 유사해서 BFS만 알아두면 저 두 알고리즘도 거저 먹는거나 마찬가지이다.
어제 오늘 BFS에 관한 문제를 많이 풀었으니 다음에는 DFS도 까먹지 않게 DFS 문제도 다시 풀어봐야겠다.
