https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
이번문제는 BFS(Breadth-First Search) 를 사용하여 해결하는 미로탐색 알고리즘의 응용 문제이다.
일단 위의 문제를 푸는 로직은 아래와 같다.
<첫번째 로직>
1. 미로의 map (행렬)을 만들어 탐색을 수행한다.
2. 미로와 같은 행렬의 크기인 새로운 행렬 visit(방문확인 행렬) 을 생성한다. 단, 해당 방문행렬의 요소들은
처음부터 모두 정수의 최대값으로 초기화 시켜준다.
3. Node class 를 생성하여 해당 노드에 행,열 위치정보와 현재 몇칸을 건너왔는지에 대한정보 그리고 몇개의 벽을 쉈는지에 대한 정보를 넣어준다.
4. 해당 Node 객체를 가지고 Queue 를 생성하여 Enqueue Dequeue 를 반복하여 Queue 에 Node 객체가 사라질 때까지 너비탐색을 진행하여 미로를 탐색해준다.
5. Enqueue Dequeue 작업에서는 너비탐색으로 다음위치로 향할 경우에 해당 위치가 벽인지 아닌지 체크하고 방문배열도 체크해준다.
6. Queue 에 모든 객체요소가 사라지거나 Queue 에 존재하는 Node 객체의 row,col 정보가 맨 마지막 row,col 인 경우에멈춰주고 답을 도출한다.
예시를 들기위해서 아래와 같은 미로가 존재한다고 해보자.
첫번째 경우는 아래와 같은 경우를 생각해 볼 수 있다.
벽을 한번은 깰수 있으므로 벽을 깨서 나가거나 벽이 없는 길로 나가는 방법이 존재한다
즉, 다음번에는 두가지의 사건으로 나뉘게 되는데 1의 사건인 경우에는 또 다시 오른쪽으로 이동하여 진행할 수 있고,
아직 벽을 부순적이 없으므로아래의 벽을 부수고 지나갈 수 도 있다. 하지만 2의 사건의 경우에는이미 벽을 한번 부수고
진행하였으므로 더 이상 벽을 부술 수 없다. 즉 해당 사건은 끝나게 된다.
다음의 경우는 아래와 같다. 아래의 그림에서도 1 사건의 경우는 벽이 없는 오른쪽으로 진행 가능하고
또한 1사건은 벽을 부순적 없으니 아래방향으로도 이동 가능하다. 또한 2사건의 경우는 이미 벽을 한번 부순적이 있으므로
오른쪽 방향으로 이동은 불가능하지만 아래 방향으로는 이동이 가능하다.
(빨간색 배경에 하얀글씨로 적어진 X 표시는 "더이상 방법이 없다." 라는 표시이다.)
즉, 위와 같은 논리로 계속 진행하다 보면 아래와 같은 결과가 나오게 된다.
1. JAVA
import java.io.*;
import java.util.*;
public class Main
{
static int N,M;
static int[][] map;
static int[][] visit;
static int[] dr = {1,-1,0,0};
static int[] dc = {0,0,1,-1};
static int amt = Integer.MAX_VALUE;
//어떤 행렬에 있고 현재 몇칸째 이동중인지 전에 벽을 부쉈는지 정보를 저장해주는 객체
static class Node {
int r,c,step,drill;
public Node(int r, int c, int step, int drill) {
this.r = r;
this.c = c;
this.step = step;
this.drill = drill;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] rc = br.readLine().split(" ");
N = Integer.parseInt(rc[0]);//행
M = Integer.parseInt(rc[1]);//열
map = new int[N][M];//map 행렬 선언
visit = new int[N][M];// visit 행렬 선언
//초기화 작업
for (int i = 0; i < N; i++) {
String[] elemnts = br.readLine().split("");
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(elemnts[j]);
visit[i][j] = Integer.MAX_VALUE;//visit 행렬은 모두의 element 를 정수 최대값으로 초기화 해준다.
}
}
bfs(0,0);
if (amt == Integer.MAX_VALUE) amt = -1;
bw.write(amt + "");
bw.close();
br.close();
}
static void bfs(int r, int c) {
//첫번째 행,렬의 정보와 첫번째 칸이라는 정보 그리고 아직 벽을 뚫은적이 없으니 drill은 0으로 초기화
Node node = new Node(r,c,1,0);
Queue<Node> queue = new LinkedList<>();
queue.offer(node);
while(!queue.isEmpty()) {
Node nd = queue.poll();
//마지막 행렬의 정보인 경우
if (nd.r == N-1 && nd.c == M-1) {
amt = nd.step;
break;
}
for (int i = 0; i < 4; i++) {
int nr = nd.r + dr[i];
int nc = nd.c + dc[i];
if (nr < 0 || nc < 0 || nr >= N || nc >= M || visit[nr][nc] <= nd.drill) continue;
if (map[nr][nc] == 0) {
visit[nr][nc] = nd.drill;
queue.offer(new Node(nr,nc,nd.step + 1,nd.drill));
} else if (nd.drill == 0) {
visit[nr][nc] = nd.drill;
queue.offer(new Node(nr,nc,nd.step + 1,nd.drill + 1));
}
}
}//while
}
}
2. C++
#include <iostream>
#include <algorithm>
#include <queue>
#include <limits.h>
using namespace std;
int N,M;
int** map;
int** visit;
int dr[4] = {1,-1,0,0};
int dc[4] = {0,0,1,-1};
int amp = INT_MAX;
void bfs(int r, int c);
typedef struct {
int r,c,step,drill;
} nods;
int main() {
scanf("%d %d",&N,&M);
map = new int*[N];
visit = new int*[N];
for (int i = 0; i < N; i++) {
map[i] = new int[M];
visit[i] = new int[M];
}
char line[M+1];
for (int i = 0; i < N; i++) {
scanf("%s",line);
for (int j = 0; j < M; j++) {
map[i][j] = line[j] - '0';
visit[i][j] = INT_MAX;
}
}
bfs(0,0);
if (amp == INT_MAX) printf("-1");
else printf("%d",amp);
return 0;
}
void bfs(int r, int c) {
queue<nods> q;
q.push({r,c,1,0});
while(!q.empty()) {
nods nd = q.front();
q.pop();
if (nd.r == N-1 && nd.c == M-1){
amp = nd.step;
break;
}
for (int i = 0; i < 4; i++) {
int nr = nd.r + dr[i];
int nc = nd.c + dc[i];
if (nr < 0 || nc < 0 || nr >= N || nc >= M || visit[nr][nc] <= nd.drill) continue;
if (map[nr][nc] == 0) {
visit[nr][nc] = nd.drill;
q.push({nr,nc,nd.step+1,nd.drill});
} else if (nd.drill == 0) {
visit[nr][nc] = nd.drill;
q.push({nr,nc,nd.step+1,nd.drill+1});
}
}
}
}
<두번째 로직>
1. 미로의 map (행렬)을 만들어 탐색을 수행준비.
2. 미로와 같은 행렬의 크기인 새로운 행렬 visit(방문확인 행렬) 을 생성한다. visit[x][y][z] 라고 했을 경우
x는 row 의 위치 y는 col 의 위치 z는 몇번째 벽을 부쉈는지의 index 로 mapping 시켜준다.
해당 3차 배열은 boolean 형으로 생성해준다. => 최대 부술수 있는 벽이 하나이므로 z 는 2로 설정한다.
3. Node class 를 생성하여 해당 노드에 행,열 위치정보와 현재 몇칸을 건너왔는지에 대한정보 그리고 몇개의 벽을 쉈는지에 대한 정보를 넣어준다.
4. 해당 Node 객체를 가지고 Queue 를 생성하여 Enqueue, Dequeue 를 반복하여 Queue 에 Node 객체가 사라질 때까지 너비탐색을 진행하여 미로를 탐색해준다.
5. Enqueue Dequeue 작업에서는 너비탐색으로 다음위치로 향할 경우에 해당 위치가 벽인지 아닌지 체크하고 방문배열도 체크해준다.
6. Queue 에 모든 객체요소가 사라지거나 Queue 에 존재하는 Node 객체의 row,col 정보가 맨 마지막 row,col 인 경우에멈춰주고 답을 도출한다.
예시를 들기위해 아래와 같은 map이 존재한다고 해보자.
첫번째 칸을 방문하였으므로 방문배열에는 아래와 같이 표시해주면 된다 표시가 안되어있는 칸은 모두 false 라고 생각하면 된다. 빨간점으로 표시된 부분은 true 값이라고 생각하면 된다.
그 다음으로 방향을 아래쪽으로 향한다고 가정하자.
그럼 아래와 같은 map 의 결과가 나올 것이다.
해당 결과에 대한 방문배열결과는 아래와 같이 표시할 수 있다.
위와같은 로직으로 코딩을 하면 아래와 같이 쓸 수 있다.
1. JAVA
import java.io.*;
import java.util.*;
public class Main {
static int N,M;
static int[][] map;
static boolean[][][] visit;
static int[] dr = {0,0,-1,1};
static int[] dc = {1,-1,0,0};
static class Node {
int r,c,step,crush;
public Node(int r,int c,int step,int crush) {
this.r = r;
this.c = c;
this.step = step;
this.crush = crush;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] inputs = br.readLine().split(" ");
N = Integer.parseInt(inputs[0]);
M = Integer.parseInt(inputs[1]);
map = new int[N][M];
visit = new boolean[N][M][2];
for (int i = 0; i < N; i++) {
String[] cols = br.readLine().split("");
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(cols[j]);
}
}
int result = bfs();
bw.write(result + "");
bw.close();
br.close();
}
static int bfs() {
Queue<Node> queue = new ArrayDeque<>();
visit[0][0][0] = true;
queue.offer(new Node(0,0,1,0));
while(!queue.isEmpty()) {
Node nod = queue.poll();
if (nod.r == N-1 && nod.c == M-1) {
return nod.step;
}
for (int i = 0; i < 4; i++) {
int nr = nod.r + dr[i];
int nc = nod.c + dc[i];
if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
//벽이 없는 경우
if (map[nr][nc] == 0 && !visit[nr][nc][nod.crush] ) {
queue.offer(new Node(nr,nc,nod.step+1,nod.crush));
visit[nr][nc][nod.crush] = true;
}
if (map[nr][nc] == 1 && nod.crush < 1 && !visit[nr][nc][nod.crush+1]) {
queue.offer(new Node(nr,nc,nod.step+1,nod.crush+1));
visit[nr][nc][nod.crush+1] = true;
}
}
}//while
return -1;
}
}
2. C++
#include <iostream>
#include <queue>
using namespace std;
int N,M;
int** map;
bool visit[1001][1001][3];
int dr[4] = {0,0,-1,1};
int dc[4] = {1,-1,0,0};
int bfs();
typedef struct {
int r,c,step,crush;
} nods;
int main()
{
scanf("%d %d",&N,&M);
map = new int*[N];
for (int i = 0; i < N; i++) map[i] = new int[M];
char line[M+1];
for (int i = 0; i < N; i++) {
scanf("%s",line);
for (int j = 0; j < M; j++) {
map[i][j] = line[j] - '0';
}
}
printf("%d",bfs());
}
int bfs() {
queue<nods> q;
nods nn = {0,0,1,0};
q.push(nn);
visit[0][0][0] = true;
while(!q.empty()) {
nods nd = q.front();
q.pop();
if (nd.r == N-1 && nd.c == M-1) {
return nd.step;
}
for (int i = 0; i < 4; i++) {
int nr = nd.r + dr[i];
int nc = nd.c + dc[i];
if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
if (map[nr][nc] == 0 && !visit[nr][nc][nd.crush]) {
nods ns = {nr,nc,nd.step+1,nd.crush};
q.push(ns);
visit[nr][nc][nd.crush] = true;
}
if (map[nr][nc] == 1 && nd.crush < 1 && !visit[nr][nc][nd.crush+1]) {
nods ns = {nr,nc,nd.step+1,nd.crush+1};
q.push(ns);
visit[nr][nc][nd.crush+1] = true;
}
}
}
return -1;
}'코딩 테스트' 카테고리의 다른 글
| 백준 16933번 - 벽 부수고 이동하기3 (2) | 2022.02.11 |
|---|---|
| 백준 14442번 - 벽 부수고 이동하기2 (1) | 2022.02.08 |
| 백준 14503번 - 로봇 청소기 (0) | 2022.01.18 |
| 백준 14502번 - 연구소 (0) | 2022.01.04 |
| HackerRank - Type of Triangle(SQL) (0) | 2021.12.27 |
