백준 2206번: 벽 부수고 이동하기

문제

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

---

풀이

n×m의 행렬로 표현되는 맵에서 0은 이동할 수 있는 곳을, 1은 벽을 나타냅니다.

상하좌우로 인접한 칸으로 이동할 수 있고 벽을 1개 부술 수 있을 때 (1, 1)에서 (n, m)까지의 최단 거리를 구하는 문제입니다.

---

접근

그래프의 간선에 가중치가 없기 때문에 다익스트라 대신 bfs로 문제 해결이 가능합니다.

어떤 좌표에 방문 여부를 확인할 수 있는 visited 배열은 boolean 배열로 나타내기 위해선 해당 좌표까지 오는 최단 경로 과정에서 벽을 부쉈는지 여부까지 확인해야 하므로 3차원 배열을 사용해야 하기 때문에 메모리를 많이 차지할 뿐만 아니라 코드도 복잡해집니다.

하지만 boolean 배열이 아닌 int 배열로 나타내면 해당 좌표까지 오는 최단 경로 과정에서 벽을 몇 개 부쉈는지 나타낼 수 있기 때문에 2차원 배열을 사용할 수 있습니다.

임의의 좌표 (x, y)가 있을 때 x, y와 (1, 1)에서 (x, y)까지 최단 경로로 이동했을 때의 최단 거리 cnt, 부순 벽의 개수 breaked를 표현하는 point 클래스를 만들어 사용했습니다.

---

코드

자바

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Queue;
import java.util.LinkedList;
import java.util.StringTokenizer;

class point {
    int x, y, cnt, breaked;

    public point(int x, int y, int cnt, int breaked) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
        this.breaked = breaked;
    }
}

public class Main {

    static int n, m;
    static int[][] arr, visited;

    public static void bfs() {
        Queue<point> queue = new LinkedList<>();
        queue.offer(new point(0, 0, 1, 0)); // (2)
        visited[0][0] = 0;
        int[] dx = { -1, 0, 1, 0 };
        int[] dy = { 0, -1, 0, 1 };
        while (!queue.isEmpty()) {
            point p = queue.poll();
            if (p.x == n - 1 && p.y == m - 1) { // (3)
                System.out.println(p.cnt);
                System.exit(0);
            }
            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                    if (arr[nx][ny] == 1) { // (4)
                        if (p.breaked == 0 && visited[nx][ny] > 1) {
                            visited[nx][ny] = 1;
                            queue.offer(new point(nx, ny, p.cnt + 1, 1));
                        }
                    } else if (visited[nx][ny] > p.breaked) { // (5)
                        visited[nx][ny] = p.breaked;
                        queue.offer(new point(nx, ny, p.cnt + 1, p.breaked));
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n][m];
        visited = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(visited[i], 2); // (1)
            String str = br.readLine();
            for (int j = 0; j < m; j++) {
                arr[i][j] = str.charAt(j) - '0';
            }
        }
        bfs();
        System.out.println(-1); // (6)
    }
}

(1) visited 배열의 모든 값을 2로 초기화합니다.

추후에 bfs 함수에서 해당 좌표의 방문 가능 여부를 확인하기 위함인데 1보다 큰 수로만 초기화하면 됩니다.

모든 입력이 끝나면 bfs 함수로 들어갑니다.

 

(2) bfs 함수 내부에서의 큐는 point가 들어가며 시작하는 칸(1, 1)의 초기 point(0, 0, 1, 0)을 큐에 삽입합니다.

시작하는 칸과 끝나는 칸도 포함해서 세기 때문에 cnt는 1이고 시작하는 칸은 0이기 때문에 breaked은 0입니다.

또한 문제에서는 좌표의 위치가 (1, 1)부터 (n, m)까지 있지만 저는 (0, 0)부터 (n - 1, m - 1)까지입니다.

시작하는 칸의 visited 값을 0으로 초기화한 후에 큐에서 poll한 값을 p라고 했을 때 큐가 비어있지 않을 때까지 아래의 과정을 반복합니다.

 

(3) p의 위치가 (n, m)이라면 p의 cnt를 출력하고 프로그램을 종료합니다.

앞서 말씀드렸듯이 저는 좌표를 (0, 0)부터 (n - 1, m - 1)까지로 설정했기 때문에 p.x가 n - 1, p.y가 m - 1일 때입니다.

 

(4) 그다음 탐색 위치(nx, ny)가 가능한 위치이며 해당 칸이 벽인지 아닌지 확인합니다.

벽이라면 p.breaked는 0이어야 합니다. 또한 visited[nx][ny]가 1이라면 이미 해당 벽을 부순 최단 경로가 존재하기 때문에 아예 방문한 적이 없어야 한다는 의미로 visited[nx][ny]는 초기값, 즉 1보다 큰 값이어야 합니다.

위의 조건을 만족했다면 visited[nx][ny]는 1로 초기화해주고 큐에 (nx, ny, p.cnt + 1, 1)을 삽입합니다.

 

(5) 그 다음칸이 벽이 아니라면 visited[nx][ny]가 p.breaked보다 큰지 확인합니다.

p.breaked가 1이면 방문하지 않았을 경우인 visited[nx][ny]가 초기값, 즉 1보다 큰 값인 경우에만 이동할 수 있습니다.

p.breaked가 0이면 다른 벽을 부수는 방법이 더 빠를 수도 있기 때문에 visited[nx][ny]가 1이어도 이동할 수 있습니다.

p.breaked와 visited[nx][ny]가 같은 경우는 벽을 부순 개수가 같은데 이미 방문한 적이 있다는 뜻으로 최단 거리를 구해야 하는 문제에서 쓸모가 없기 때문에 넘어갑니다.

위의 조건을 만족했다면 visited[nx][ny]는 p.breaked로 초기화해주고 큐에 (nx, ny, p.cnt + 1, p.breaked)을 삽입합니다.

 

(6) bfs 함수가 끝났음에도 프로그램이 종료되지 않았다면 -1을 출력합니다.

목표 지점까지 도달하지 못했단 뜻이기 때문입니다.

C언어

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int n, m, **arr, **visited, result = -1;
typedef struct {
	int x, y, cnt, breaked;
} Point;
typedef struct node {
	Point point;
	struct node* next;
} node;
typedef struct Queue {
	node* front;
	node* rear;
	int count;
} Queue;
void initQueue(Queue* queue) {
	queue->front = queue->rear = NULL;
	queue->count = 0;
}
void push(Queue* queue, int x, int y, int cnt, int breaked) {
	node* now = (node*)malloc(sizeof(node));
	now->point.x = x;
	now->point.y = y;
	now->point.cnt = cnt;
	now->point.breaked = breaked;
	now->next = NULL;
	if (queue->count == 0) {
		queue->front = now;
	}
	else {
		queue->rear->next = now;
	}
	queue->rear = now;
	queue->count++;
}
Point pop(Queue* queue) {
	Point re;
	node* now;
	now = queue->front;
	re = now->point;
	queue->front = now->next;
	free(now);
	queue->count--;
	return re;
}
int empty(Queue* queue) {
	if (queue->count == 0) return 1;
	else return 0;
}
void bfs() {
	Queue queue;
	initQueue(&queue);
	push(&queue, 0, 0, 1, 0);
	visited[0][0] = 0;
	int dx[] = { -1, 0, 1, 0 };
	int dy[] = { 0, -1, 0, 1 };
	while (!empty(&queue)) {
		Point p = pop(&queue);
		if (p.x == n - 1 && p.y == m - 1) {
			printf("%d", p.cnt);
			exit(0);
		}
		for (int i = 0; i < 4; i++) {
			int nx = p.x + dx[i];
			int ny = p.y + dy[i];
			if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
				if (arr[nx][ny] == 0) {
					if (p.breaked == 0 && visited[nx][ny] > 1) {
						visited[nx][ny] = 1;
						push(&queue, nx, ny, p.cnt + 1, 1);
					}
				}
				else if (visited[nx][ny] > p.breaked) {
					visited[nx][ny] = p.breaked;
					push(&queue, nx, ny, p.cnt + 1, p.breaked);
				}
			}
		}
	}
}
main() {
	scanf("%d %d", &n, &m);
	arr = (int**)malloc(sizeof(int**) * n);
	visited = (int**)malloc(sizeof(int**) * n);
	char* str = (char*)malloc(sizeof(char) * m + 1);
	for (int i = 0; i < n; i++) {
		scanf("%s", str);
		arr[i] = (int*)malloc(sizeof(int) * m);
		visited[i] = (int*)malloc(sizeof(int) * m);
		memset(visited[i], 2, sizeof(int) * m);
		for (int j = 0; j < m; j++) {
			arr[i][j] = str[j] - '0';
		}
	}
	free(str);
	bfs();
	printf("-1");
}

자바를 이용한 풀이와 동일합니다.

---

결론

bfs 함수 내부에서 문제 풀이를 더 원활하게 설명하기 위해서 깃허브에 올라간 코드에서 사용한 조건문의 순서를 좀 바꿔서 작성해봤습니다. 속도면에서 큰 차이는 있지 않습니다.

또한 이번 문제부터 새로운 피드백을 받아 문제와 코드 사이에 문제를 접근했던 방식을 추가로 작성하게 되었습니다.