이번 주부터 저희 스터디는 여태까지 공부했던 알고리즘들을 다시 한 번 복습하자는 의미로 알고리즘 문제를 선정하여 풀고 있습니다.
이번 주에는 DFS / BFS에 관한 문제를 풀었습니다.
📌 불!
불! 문제는 간단하게 설명하자면, 불에 타고 있는 미로에 지훈이가 갇혀 있는데 지훈이가 불에 타기 전, 지훈이가 탈출할 수 있는지의 여부와 얼마나 빨리 탈출할 수 있는지 시간을 출력하는 문제입니다.
탈출할 수 없는 경우는 IMPOSSIBLE을 출력하도록 합니다.
아래와 같이 입력이 주어집니다.
4 4
####
#JF#
#..#
#..#J는 지훈이를 의미하고, F는 불을 의미하며 .은 지나갈 수 있는 공간입니다. 또한 #은 벽을 의미합니다.
이때, 불은 매 분마다 대각선으로 말고, 수평/수직으로만 이동하여 확산됩니다.
위의 예제에서는 지훈이는 불에 타기 전에 탈출할 수 있고 3이라는 시간이 걸립니다.
💡 느낀점과 배운점
이 문제를 보고 큰 틀은 BFS를 통해 해결하면 되겠다는 생각은 했지만 BFS를 어떤 식으로 이용할지는 생각이 나질 않았습니다.
그래서 먼저 해결하신 다른 분들 것을 참고했습니다.
일반적으로 DFS/BFS를 구현한다고 하면 visited같이 방문한 노드에 방문 처리를 해주는 배열을 선언해주는데, 이를 선언해주지 않으면 방문했던 노드에 계속 방문하게 됩니다.
여튼 참고한 코드에는 이 visited 배열을 두 개 사용하여 해결하였습니다.(물론 한 개만 사용하여 푸신 분들도 있었습니다.)
이 visited 배열에는 지훈이가 이동한 표시와 불이 이동한 표시 총 2개를 사용하였고, BFS를 구현하는 데 필요한 Queue도 지훈이와 불의 좌표를 저장하기 위해 2개 사용하였습니다.
특히 이번 문제를 보면서 배운 점은 기본적인 BFS 문제만 풀어봐서 하나의 메서드만 구현하여 해결하였는데, 이 문제 같은 경우 지훈이가 탐색하기 위한 BFS와 불이 탐색할 BFS, 총 두 개의 메서드를 구현하여 해결하였습니다.
그래서 이 두 개의 BFS를 어떻게 구현하여 어떤식으로 이용하여 해결하였을까?
바로 불을 먼저 BFS를 통해 이동시킨 다음 지훈이를 BFS를 통해 이동시키는 방식으로 해결합니다.
아래의 코드는 불에 대한 BFS 입니다.
public static void fireBfs() {
int size = fire.size();
for(int i=0; i<size; i++){
Node node = fire.poll();
for(int d=0; d<4; d++) {
int x = node.x + dx[d];
int y = node.y + dy[d];
if (!(x >= 0 && y >= 0 && x < r && y < c)) continue;
if (fireVisit[x][y]) continue;
if (maze[x][y] == '#') continue;
maze[x][y] = 'F';
fireVisit[x][y] = true;
fire.add(new Node(x, y, 0));
}
}
}불을 먼저 이동시키며 이동시킨 좌표가 주어진 미로의 범위 안에서만 이동하고 방문하지 않았고, 벽이 아니라면 그 위치에 불을 확산시킵니다.
그 다음 지훈이를 움직입니다.
아래는 지훈이에 대한 BFS입니다.
public static void bfs() {
while(!person.isEmpty()){
fireBfs();
int size = person.size();
for(int i=0; i<size; i++){
Node node = person.poll();
if(node.x==0 || node.x==r-1 || node.y==0 || node.y==c-1){
answer = node.cnt + 1;
return;
}
for(int d=0; d<4; d++){
int x = node.x + dx[d];
int y = node.y + dy[d];
if(!(x>=0 && y>=0 && x<r && y<c)) continue;
if(personVisit[x][y]) continue;
if(maze[x][y] == 'F' || maze[x][y] == '#') continue;
person.add(new Node(x, y, node.cnt+1));
personVisit[x][y] = true;
}
}
}
}불에 대한 BFS 코드와 유사하지만, 불에 대한 BFS를 통해 불을 먼저 이동시킨 다음에 지훈이가 이동하는 코드입니다.
지훈이가 탈출하게 되면 빠져나올 코드와, 지훈이가 이동할 때마다 count를 하도록 구현되어 있습니다.
이런 식으로 불을 먼저 이동시킨 다음에 지훈이를 이동시키는게 한 사이클로 동작합니다.
DFS/BFS 문제를 이런 식으로 응용한 문제들을 풀 수 있도록 좀 더 바라보는 시각을 다각화하도록 해야겠다고 느꼈습니다.
📌 Most Stones Removed with Same Row or Column
이 Most Stones Removed with Same Row or Column 문제를 간단하게 설명하자면, 2차원 평면 위에 돌들이 존재합니다. 이 돌들을 제거할 수 있는데, 제거되지 않은 돌 중에서 같은 행이나 같은 열을 공유하고 있다면 제거될 수 있습니다.
이런 식으로 가능한 최대한 많이 제거하여 그 제거된 돌의 개수를 출력하는 문제입니다.
문제에서는 [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]와 같이 돌들의 좌표가 주어집니다.
이 입력을 2차원 평면 위에 나타낸다면 아래와 같이 나타낼 수 있습니다.
1 1
1 1
1 1위의 있는 돌들은 최대 5개를 제거할 수 있습니다.
💡 느낀점과 배운점
이 문제 역시 참고했는데, 코드를 보면 되게 간단해 보이지만 생각하기 쉽지 않았을 것 같습니다.
이 문제는 DFS를 통해 해결할 수 있습니다.
아래의 코드를 먼저 보겠습니다.
private static boolean[] visited; // 방문 여부
public int removeStones(int[][] stones) {
visited = new boolean[stones.length];
int answer = 0;
for(int i=0; i<stones.length; i++){
// 방문하지 않았다면
if(!visited[i]){
answer++;
// dfs 탐색
dfs(i, stones.length, stones);
}
}
return stones.length - answer;
}돌들의 개수만큼 for 문을 반복하면서 방문하지 않은 노드(돌)에 대해서만 동작하도록 합니다.
그리고 바로 answer 변수를 count하는데, 이를 이용하여 나중에 최종 결과는 돌들의 개수 - answer를 하여 최대한 제거된 돌의 개수를 출력하도록 합니다.
answer는 돌이 하나라도 존재한다면 최소 1이 되어야 하는데, 이유는 돌이 최대한 제거되어도 무조건 하나는 남게되어 있을 것이기 때문입니다.
그리고 아래의 호출한 DFS 코드를 보겠습니다.
public void dfs(int idx, int size, int[][] stones){
// 방문 표시
visited[idx] = true;
for(int i=0; i<size; i++){
// 방문하지 않았고
if(!visited[i]){
// 같은 행이거나 같은 열이면
if(stones[idx][0] == stones[i][0] || stones[idx][1] == stones[i][1]){
// dfs 호출
dfs(i, size, stones);
}
}
}
return;
}vistied 배열을 통해 먼저 방문한 노드에 방문 처리를 해줍니다.
그 뒤로 돌들의 개수만큼 for 문을 통해 반복하는데, 방문하지 않은 노드(돌)에 대해서만 동작하도록 합니다.
그 다음 if 문이 코드에서 중요한 부분인데, 현재 돌의 좌표에서 같은 행이거나 같은 열에 돌이 존재하면 dfs를 재귀호출 하여 그 돌의 위치로 이동합니다.
이런 식으로 다른 좌표로 이동할 때마다 같은 행 또는 같은 열에 돌이 존재하는지 계속 탐색합니다.
그래서 위의 예제에서 돌의 좌표에 따르면 answer 변수를 1 증가시킨 상태에서 DFS를 호출하게 되면 모든 돌들을 다 탐색하게 될 것입니다.
왜냐하면 if 문에 따르면 현재 좌표에서 같은 행 또는 같은 열에 돌이 존재하고, 그 돌에 방문하지 않았을 때 탐색하도록 했으니 모든 돌을 탐색했으며, DFS를 탈출하게 되면 모든 돌을 탐색했으니 더 이상 탐색할 수 없어서 for 문을 종료합니다.
그러면 돌들의 개수(6) - answer(1)를 하게 되면 최종 결과는 5가 됩니다.
이 문제를 보면서 DFS를 통해 바로 옆에 인접하게 있는 노드를 탐색하는 것뿐만 아니라 같은 행이거나 같은 열이면 이동하여 탐색할 수 있도록하여 해결할 수 있다는 것을 배웠습니다.
