mingssssss

1. 문제

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

2. 코드

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

public class Main {

	static ArrayList<ArrayList<Character>> list;
	static int[][] dist;
	static Queue<int[]> q;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static boolean[][][] visited;
	static int N;
	static int M;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		list = new ArrayList<>();

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		dist = new int[N][M];
		visited = new boolean[2][N][M];

		for (int i = 0; i < N; i++) {
			list.add(new ArrayList<>());
		}

		for (int i = 0; i < N; i++) {
			char[] c = br.readLine().toCharArray();
			for (int j = 0; j < M; j++) {
				list.get(i).add(c[j]);
			}
		}
		// 입력 종료

		// 시작 지점과 도착 지점이 같은 경우
		if (N - 1 == 0 && M - 1 == 0) {
			System.out.println(1);
			System.exit(0);
		}

		// Queue 초기화 후 시작 지점과 벽을 부순 여부를 Queue에 넣어줌
		q = new LinkedList<>();
		q.add(new int[] { 0, 0, 0 });

		bfs();

	}

	private static void bfs() {

		while (!q.isEmpty()) {

			int[] now = q.poll();

			for (int i = 0; i < 4; i++) {

				int nextX = now[0] + dx[i];
				int nextY = now[1] + dy[i];
				int crush = now[2];

				if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
					continue;
				}

				// 벽인 경우
				if (list.get(nextX).get(nextY) == '1') {
					// 충돌하지 않았으면서, 방문한적이 없다면, 방문 처리, 거리 추가, 큐에 좌표 넣어주기
					if (crush == 0 && visited[crush][nextX][nextY] == false) {
						visited[crush][nextX][nextY] = true;
						dist[nextX][nextY] = dist[now[0]][now[1]] + 1;
						q.add(new int[] { nextX, nextY, 1 });
					}
				} else {

					// 충돌 여부에 따른 방문 처리를 한 적이 없는 경우
					if (visited[crush][nextX][nextY] == false) {

						visited[crush][nextX][nextY] = true;
						dist[nextX][nextY] = dist[now[0]][now[1]] + 1;
						q.add(new int[] { nextX, nextY, crush });
					}

				}
				// 도착 지점에 도달했을 때
				if (nextX == (N - 1) && nextY == (M - 1)) {
					System.out.println(dist[nextX][nextY] + 1);
					System.exit(0);
				}

			}
		}
		// 도착할 수 없는 경우
		System.out.println(-1);
	}
}

3. 리뷰

벽을 한 번만 선택해서 부서서 시작 지점(0, 0)부터 도착 지점(N, M)까지

최소 이동횟수를 구하는 문제이다.

입력값이 최대가 1000이니까 모든 벽을 부수면서 이동하는 것은 시간초과가 난다.

브루트포스 알고리즘으로 모든 벽을 부수면서 진행했는데 시간초과가 났다.

그래서 구글링을 통해 방문함수를 3차원으로 설정해서 벽을 부수고 지나가는 경우와

벽을 부수지 않고 지나가는 두 가지의 경우를 고려하여 풀었다.

먼저 시작지점과 도착지점이 같은 경우, 이동횟수 1로 바로 도착할 수 있으므로 설정하고,

그게 아닌 경우 Queue에 시작 지점과 도착 지점, 벽을 부섰는지의 여부를 넣고

bfs를 돌렸다.

다음에 탐색할 값이 벽인 경우에, 한 번도 벽을 부순 적이 없으면서 방문하지 않았다면

벽을 부수지 않은 방문 배열에(crush의 값이 0) 방문 체크를 하고

현재 거리에서 1만큼 추가하여 dist 배열에 저장하고 Queue에 집어넣었다.

만약 벽을 만나지 않은 경우에 방문하지 않았다면,

crush의 여부에 따라 해당 방문 배열에 방문 체크를 하고 동일하게 거리 저장 후

Queue에 집어넣었다.

도착 지점에 도달한 경우, dist[nextX][nextY]의 값에 1를 추가하고 출력했다.

while문을 빠져나온 경우, 도착 지점에 도달하지 못 했으므로, -1을 출력한다.

bfs 골드 문제부터 3차원 배열을 사용하여 문제를 푸는 경우가 많은데,

이런 유형의 문제가 많은 것 같아서 사용법을 잘 숙지하고

다른 문제에도 적용할 수 있게 공부해야겠다.