BOJ_G4_1261

📁 [G4_1261] 알고스팟

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

public class Main {
	static int N, M, min, cnt;
	static int[][] map;
	static int[][] v;
	static int[] dx = { 0, 0, 1, -1 };
	static int[] dy = { 1, -1, 0, 0 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		// 가로크기
		M = Integer.parseInt(st.nextToken());

		// 세로 크기
		N = Integer.parseInt(st.nextToken());

		// 1,1 부터 시작한다
		map = new int[N + 1][M + 1];

		// 누적 비용
		v = new int[N + 1][M + 1];

		// 입력
		for (int i = 1; i < N + 1; i++) {
			String str = br.readLine();
			String[] sstr = str.split("");
			for (int j = 1; j < M + 1; j++) {
				map[i][j] = Integer.parseInt(sstr[j-1]);
				v[i][j] = Integer.MAX_VALUE;
			}
		}

		v[1][1] = 0;
		bfs(1, 1);

		System.out.println(v[N][M]);
	}

	// bfs
	static void bfs(int x, int y) {
		Queue<int[]> q = new LinkedList<int[]>();
		
		q.offer(new int[] {x,y});
		
		while(!q.isEmpty()) {
			int cur[] = q.poll();
			
			for(int i=0; i<4; i++) {
				int nx = cur[0] + dx[i];
				int ny = cur[1] + dy[i];
				
				// 범위 벗어나는 경우
				if(nx < 1 || ny < 1 || nx > M || ny >N ) continue;
				
				// 벽인 경우 && 누적되는 비용이 더 많이 드는 경우 갱신
				if(map[ny][nx] == 1 && v[ny][nx] > v[cur[1]][cur[0]]+1) {
					v[ny][nx] = v[cur[1]][cur[0]]+1;
					q.offer(new int[] {nx,ny});
				}
				// 벽이 아닌 경우 && 누적되는 비용이 더 많이 드는 경우 갱신 -> 1을 더할 필요가 없다
				else if(map[ny][nx] == 0 && v[ny][nx] > v[cur[1]][cur[0]]) {
					v[ny][nx] = v[cur[1]][cur[0]];
					q.offer(new int[] {nx,ny});
				}
			}
		}
	}
}

🤔 나의 생각

처음에 문제를 보자마자 간단한 시뮬레이션이구나~ 하고 dfs로 딱 풀었는데 시간초과가 떴다..
원래 v[][] 를 boolean으로 방문체크로 했는데 그것보다 bfs를 활용하여 int형 배열로 누적되는 비용을 저장해서 계속 갱신해 나가야 겠다고 생각이 들었다.
그래서 queue를 이용해 bfs를 구현했다.
다음 공간에 벽이 있을 경우 기존 비용에다 +1 을 해서 다음 비용과 비교를 해 더 적은 경우를 선택해 주었고
다음 공간에 벽이 없을 경우 기존 비용 그대로 해서 다음 비용과 비교를 해 더 적은 경우를 선택해 주었다.
시간복잡도를 잘 생각해야 할 문제이다.