알고리즘/그래프
[BOJ] 백준 2206 - 벽 부수고 이동하기 풀이
송승현(SSH)
2023. 3. 12. 22:40
1. 문제
https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
2. 풀이 Point
<Error Point>
- (1) 벽을 만날 때마다 벽을 부수고 bfs 돌리는건 시간 초과가 난다.
- 벽을 탐색한다면 NM의 시간이 걸리고 이에 대하여 각각 bfs로 탐색하므로 (NM)^2의 시간이 걸린다.
- (2) 벽을 부쉈는지 안 부쉈는지 객체 안에 flag 변수를 두거나 visited 배열을 boolean으로 두는 경우는 탐색을 할 수가 없거나 잘못된 값을 반환한다.
- (3) visited를 int 타입의 2차원 배열로 만들자
- (3-1) 전부 0으로 초기화
- 전부 0으로 초기화를 해주면 bfs 탐색 조건문에서 현재 탐색하려고 하는 객체의 visitedCnt보다 visited 배열의 값이 작아야 하는데 (visited[xf][yf] < poll.visitedCnt), (ex : visited 값 : 0, 1번 벽을 부수고 온 경우 : 1), 이러면 위 사진과 같이 벽이 없는 부분을 따라온 경우는 초록색 부분으로 갈 수 없다. (ex : 1번 벽을 부수고 온 경우 : 1, 0만을 탐색해온 경우 : 0)
- (3-1) 전부 0으로 초기화
<풀이 Point>
- visited 배열을 int형으로 선언한다!!(boolean으로 처리시 위와 같은 사례가 발생할 수 있음)
- 입력을 받을 때 visited 배열을 2로 초기화( 어차피 벽은 1번 밖에 못 부시므로 탐색하면서 갱신하는 visited의 값은 0, 1만을 가진다. 따라서 나올 수 없는 값 중 최대 값인 2로 초기화 시켜준다.)
- 그 후 bfs를 돌면서 벽이 나오는 경우 or 벽이 아닌 경우의 분기를 설정해준다.
- 벽이 나오는 경우
- 벽이 나오는 경우는 현재 객체의 visitedCnt 값을 봐줘야 한다.
- 현재 객체의 visitedCnt 값이 0인 경우
- 이 경우는 지금까지 벽을 부순적이 한번도 없으므로 벽을 부수고 갈 수 있는 경우가 있다. 따라서 visitedCnt 값을 하나 증가시켜 준 후 큐에 넣는다.
- 현재 객체의 visitedCnt 값이 0이 아닌 경우
- 이 경우는 벽을 부순 전적이 있는 것이다. 벽은 한 번밖에 못 부수므로 이는 탐색할 수 없다.
- 현재 객체의 visitedCnt 값이 0인 경우
- 벽이 나오는 경우는 현재 객체의 visitedCnt 값을 봐줘야 한다.
- 벽이 아닌 경우
- 벽이 아닌 경우는 move를 하나 증가시켜준 후 다시 큐에 넣으면 된다.
- 벽이 나오는 경우
- 마지막으로 끝점에 도달했다면 그때까지 간 결과 중 최소값을 출력하고, 만약 결과값이 처음에 설정해둔 값 그대로라면 이는 목표 지점까지 가지 못한 경우이므로 “-1”을 출력한다.
3. 소스 코드
// 시간 초과 코드 : (1)번 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main {
static int N, M;
static int[][] map;
static boolean[][] visited;
static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};
static int result = Integer.MAX_VALUE;
static boolean flag = false; // 벽을 부쉇다는 플래그 (true : 부쉇음, false : 안 부쉇음)
static class Point {
int x;
int y;
int move;
public Point(int x, int y, int move) {
this.x = x;
this.y = y;
this.move = move;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
String input = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = input.charAt(j) - '0';
}
}
beforeBreakWallBFS(0, 0, 1);
if (result == Integer.MAX_VALUE) {
bw.write("-1");
} else {
bw.write(Integer.toString(result));
}
bw.flush();
bw.close();
br.close();
}
private static void beforeBreakWallBFS(int x, int y, int move) {
Queue<Point> q = new LinkedList<>();
q.add(new Point(x, y, move));
visited[x][y] = true;
while (!q.isEmpty()) {
Point poll = q.poll();
visited[poll.x][poll.y] = true;
if (poll.x == N - 1 && poll.y == M - 1){
result = Math.min(result, poll.move);
return;
}
for (int i = 0; i < 4; i++) {
int xf = poll.x + dx[i];
int yf = poll.y + dy[i];
if (xf >= 0 && xf < N && yf >= 0 && yf < M && !visited[xf][yf]) {
visited[xf][yf] = true;
// 벽을 만났는데 아직 안뚫었음
if (map[xf][yf] == 1 && !flag) {
int[][] copyMap = new int[N][M];
boolean[][] copyVisited = new boolean[N][M];
for (int j = 0; j < map.length; j++) {
copyMap[j] = map[j].clone();
}
for (int j = 0; j < visited.length; j++) {
copyVisited[j] = visited[j].clone();
}
Queue<Point> copyQ = new LinkedList<>(q);
copyMap[xf][yf] = 0;
copyVisited[xf][yf] = true;
copyQ.add(new Point(xf, yf, poll.move + 1));
flag = true;
afterBreakWallBFS(copyMap, copyQ, copyVisited);
flag = false;
} else {
q.add(new Point(xf, yf, poll.move + 1));
}
}
}
}
}
private static void afterBreakWallBFS(int[][] copyMap, Queue<Point> copyQ, boolean[][] copyVisited) {
while (!copyQ.isEmpty()) {
Point poll = copyQ.poll();
copyVisited[poll.x][poll.y] = true;
if (poll.x == N - 1 && poll.y == M - 1){
result = Math.min(result, poll.move);
return;
}
for (int i = 0; i < 4; i++) {
int xf = poll.x + dx[i];
int yf = poll.y + dy[i];
if (xf >= 0 && xf < N && yf >= 0 && yf < M && !copyVisited[xf][yf] && copyMap[xf][yf] != 1) {
copyVisited[xf][yf] = true;
copyQ.add(new Point(xf, yf, poll.move + 1));
}
}
}
}
}
<정답 코드>
// 정답 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main {
static int N, M;
static int[][] map;
static int[][] visited;
static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};
static int result = Integer.MAX_VALUE;
static class Point {
int x;
int y;
int move;
int visitedCnt; // 벽을 부순 횟수 (벽을 부쉈는지 아닌지 boolean으로는 할 수 없음)
public Point(int x, int y, int move, int visitedCnt) {
this.x = x;
this.y = y;
this.move = move;
this.visitedCnt = visitedCnt;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
visited = new int[N][M];
for (int i = 0; i < N; i++) {
String input = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = input.charAt(j) - '0';
visited[i][j] = 2; // visited 카운트를 2로 초기화, 어차피 벽은 1번 밖에 못 부시므로 1 이상의 값이 나올 수 없다.
}
}
breakWallBFS(0, 0, 1, 0);
if (result == Integer.MAX_VALUE) {
bw.write("-1");
} else {
bw.write(Integer.toString(result));
}
bw.flush();
bw.close();
br.close();
}
private static void breakWallBFS(int x, int y, int move, int visitedCnt) {
Queue<Point> q = new LinkedList<>();
q.add(new Point(x, y, move, visitedCnt));
visited[x][y] = 0;
while (!q.isEmpty()) {
Point poll = q.poll();
if (poll.x == N - 1 && poll.y == M - 1) {
result = Math.min(result, poll.move);
break;
}
for (int i = 0; i < 4; i++) {
int xf = poll.x + dx[i];
int yf = poll.y + dy[i];
if (xf >= 0 && xf < N && yf >= 0 && yf < M && (visited[xf][yf] > poll.visitedCnt)) {
// 벽을 만났음
if (map[xf][yf] == 1) {
if (poll.visitedCnt == 0) { // 지금 큐에서 꺼낸 객체(탐색하고 있는 객체)가 한번도 벽을 안 부쉈다면
visited[xf][yf] = poll.visitedCnt + 1;
q.add(new Point(xf, yf, poll.move + 1, poll.visitedCnt + 1));
}
// 지금 큐에서 꺼낸 객체(탐색하고 있는 객체)가 한번이라도 벽을 부쉈다면 벽을 또 부술 수 없으므로 기각
}
// 벽이 아닌 경우 : 그대로 탐색 진행
else if (map[xf][yf] == 0) {
visited[xf][yf] = poll.visitedCnt;
q.add(new Point(xf, yf, poll.move + 1, poll.visitedCnt));
}
}
}
}
}
}
4. 배운점
- 알고리즘의 시간초과를 잘 따져서 문제를 해결하자.(bfs : (1) 인접 행렬 : O(N^2), (2) 인접리스트 : (V + E)
- 방문 배열은 꼭 boolean일 필요 없다.(정형화된 생각을 버리자) 방문했던 곳에 또 방문할 수가 있다.
5. 점수
75/100