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

소스코드

import java.io.*;
import java.util.*;
public class Main {
	static int N, Ans;
	static int[][] map;
	static int[][] v;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		Ans = Integer.MAX_VALUE;
		map = new int[N][N];
		v = new int [N][N];
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < N; j++) {
				map[i][j] = str.charAt(j)-'0';
				v[i][j] = Integer.MAX_VALUE;
			}
		}
		bfs();
		System.out.println(Ans);
	}	
	private static void bfs() {
		Queue<Point> queue = new LinkedList<Point>();
		queue.offer(new Point(0, 0, 0));
		v[0][0] = 0;
		while(!queue.isEmpty()) {
			Point p = queue.poll();		
			if(p.r == N-1 && p.c == N-1) {
				Ans = Math.min(Ans, p.cnt);
				continue;
			}
			for (int i = 0; i < 4; i++) {
				int nr = p.r + dr[i];
				int nc = p.c + dc[i];				
				if(nr<0 || nc<0 || nr>= N || nc>= N || v[nr][nc] <= p.cnt || p.cnt >= Ans) continue;
				int visit = p.cnt;
				if(map[nr][nc] == 0) visit++;
				v[nr][nc] = visit; 
				queue.offer(new Point(nr, nc, visit));
			}
		}
	}
	private static class Point{
		int r, c, cnt;
		public Point(int r, int c, int cnt) {
			super();
			this.r = r;
			this.c = c;
			this.cnt = cnt;
		}
		@Override
		public String toString() {
			return "Point [r=" + r + ", c=" + c + ", cnt=" + cnt + "]";
		}
	}
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
}

해결방법

처음에는 3차원 방문배열을 사용하여 시도를 해본 결과 메모리 초과가 나왔다.
문제를 해결함에 있어서 방문한 곳을 갈 때는 검은 칸을 흰색칸으로 바꾸는 횟수가 더 적을 때만 방문하도록 하는 것에 중점을 두며 생각하였다.
-> 방문배열을 정수형으로 하여 해당 칸에 방의 색을 바꾸는 횟수를 저장하여 저장된 값이 현재 뒤집은 갯수보다 많을 때만 방문하여 갱신하도록 하였다.