SW 14413. 격자판 칠하기 (BFS)

SW Expert Academy

SW Expert Academy

자바

어려웠다. 그래도 가로 세로 비교해서 같은게 있으면 impossible로 구현을 했는데 런타임 오류가 자꾸나서 방법을 찾아보니까 BFS (너비우선탐색)  방법을 이용해야한다고 한다.

그래서 공부를 해보앗따.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


class Solution{
	static final int MAX_N = 10;
	static int[][] D = {{0,1},{-1,0},{1,0},{0,-1}};
	static int N;
	static int[][] Board = new int[MAX_N][MAX_N];
	static class Point {
		Point(int r,int c, int d) {
			row = r; col = c; dist=d;
		}
		int row,col,dist;
	}
	
	public static void main(String args[]) throws Exception{
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		for(int i=0;i<N;++i) 
			for(int j=0;j<N;++j) 
				Board[i][j] = sc.nextInt();

		int sRow,sCol,dRow,dCol;
		sRow = sc.nextInt(); sCol = sc.nextInt();
		dRow = sc.nextInt(); dCol = sc.nextInt();
		System.out.println(bfs(sRow,sCol,dRow,dCol));
	}

static int bfs(int sRow,int sCol,int dRow,int dCol) {
	boolean[][] visited = new boolean[MAX_N][MAX_N];
	Queue<Point> q = new LinkedList<>();
	visited[sRow][sCol] = true;
	q.add(new Point(sRow,sCol,0));
	
	while(!q.isEmpty()) {
		Point curr = q.remove();
		
		if(curr.row == dRow && curr.col ==dCol)
			return curr.dist;
	
	
	for(int i=0;i<4;++i) {
		int nr = curr.row + D[i][0], nc =  curr.col + D[i][1];
		if(nr < 0 || nr > N-1 || nc<0||nc>N-1) continue;
		if(visited[nr][nc] )continue;
		if(Board[nr][nc] ==1) continue;
		visited[nr][nc] = true;
		System.out.println("nr : "+nr+" "+"nc: "+nc+" "+curr.dist);
		q.add(new Point(nr,nc,curr.dist+1));
		}
	}
	return -1;
}
}

이건 너비우선 탐색을 이용한 최단거리 알고리즘이다. 복잡해보이지만 차근차근 보면 이해할 수 있다. 상하좌우 어느 곳을 먼저 가든지 더이상 길이 없는 것은 q에서 삭제되니까 더이상 고려가 되지 않는다.

 

BFS를 이용해서 문제를 풀어보자 ....

 

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


class Solution{
	static int D[][] = {{-1,0},{1,0},{0,-1},{0,1}};
	static int N;
	static int M;
	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i=1;i<=T;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			char arr[][] = new char[N][M];
			for(int j=0;j<N;j++) {
				String str = br.readLine();
				for(int k=0;k<M;k++) {
					char c = str.charAt(k);
					arr[j][k] = c;
					
					if(arr[j][k] =='?') {
						if(k>0) {
							if(arr[j][k-1]=='#') arr[j][k] = '.';
							else arr[j][k] = '#';
						}
						if(k ==0 && j>0) {
							if(arr[j-1][k] == '#') arr[j][k] = '.';
							else arr[j][k] = '#';
						}
					}
				}
			} 
			int ch = bfs(arr,N,M);
			if(ch == 1) System.out.println("#"+i+" "+"impossible");
			else System.out.println("#"+i+" "+"possible");
		}
	}
	public static int bfs(char arr[][],int N,int M) {
		boolean visited[][] = new boolean[N][M];
		Queue <Point> q= new LinkedList<>();
		visited[0][0] = true;
		q.add(new Point(0,0));
		int ch = 0;
		while(!q.isEmpty()) {
			Point curr = q.remove();
			
			for(int i=0;i<4;i++) {
				int nr = curr.row + D[i][0];
				int nc = curr.col + D[i][1];
				
				if(nr < 0 || nr > N-1 || nc < 0 || nc > M-1) continue;
				if(visited[nr][nc]) continue;
				if(arr[curr.row][curr.col] == arr[nr][nc]) {
					//기준노드랑 인접노드의 문자가 같으면 
					ch = 1;
					q.clear();
				}
				visited[nr][nc] = true;
				q.add(new Point(nr,nc));
			}
		}
		return ch;
	}
	static class Point {
		int row,col;
		Point(int r,int c){
			row = r; col = c;
		}
	}
}

35분만에 풀었는데 으음...... 73/68개 정답

무슨 반례가 있을까?

 

5/14 원인을 찾았따.

1
4 4
#???
????
?#??
???? 라는 입력이 있을 때

결과가

#.#. 
..#. 
.#.# 
#.#. 
#1 possible

이렇게 나왔다. 이미 ?인 구간을 거쳐서 값이 들어간 부분은 q에는 들어가지만 visited[nr][nc]가 true로 바뀌어서 더이상 점검하지 않는 것이다 ! 그래서

if(arr[nr][nc]=='?'){
	if(arr[curr.row][curr.col] == '#')	arr[nr][nc] = '.';
    else arr[nr][nc] = '#';
}

이 코드 부분을

if(arr[nr][nc] == '?') {
	if(arr[curr.row][curr.col]=='#') {
		arr[nr][nc] = '.';
		q.add(new Point(nr,nc));
		continue;
		}
	if(arr[curr.row][curr.col]=='.') {
		arr[nr][nc] = '#';
		q.add(new Point(nr,nc));
		continue;
	}
}

이렇게 바꿔주었다. visited여부를 true로 바꾸지는 않으면서 q에 넣어서 또 한 번 고려대상이 되게 함 !! 

 

full code

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


class Solution{
	static int D[][] = {{-1,0},{1,0},{0,-1},{0,1}};
	static int N;
	static int M;
	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i=1;i<=T;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			char arr[][] = new char[N][M];
			for(int j=0;j<N;j++) {
				String str = br.readLine();
				for(int k=0;k<M;k++) {
					char c = str.charAt(k);
					arr[j][k] = c;
					
				}
			} 
			
			int ch = bfs(arr,N,M);
			
			if(ch == 1) System.out.println("#"+i+" "+"impossible");
			else System.out.println("#"+i+" "+"possible");
		}
	}
	public static int bfs(char arr[][],int N,int M) {
		boolean visited[][] = new boolean[N][M];
		Queue <Point> q= new LinkedList<>();

		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(arr[i][j] != '?') {
					q.add(new Point(i,j));
				}
			}
		}
		int ch = 0;
		while(!q.isEmpty()) {
			Point curr = q.remove();
				for(int i=0;i<4;i++) {
					int nr = curr.row + D[i][0];
					int nc = curr.col + D[i][1];
					
					if(nr < 0 || nr > N-1 || nc < 0 || nc > M-1) continue;
					if(visited[nr][nc]) continue;
					if(arr[nr][nc] == '?') {
						if(arr[curr.row][curr.col]=='#') {
							arr[nr][nc] = '.';
							q.add(new Point(nr,nc));
							continue;
						}
						if(arr[curr.row][curr.col]=='.') {
							arr[nr][nc] = '#';
							q.add(new Point(nr,nc));
							continue;
						}
					}
					if(arr[nr][nc] !='?'){
						if(arr[curr.row][curr.col]=='#') {
							if(arr[nr][nc] == '#') {
								ch = 1;
								break;
							}
						}
						if(arr[curr.row][curr.col]=='.'){
							if(arr[nr][nc] == '.') {
								ch = 1;
								break;
							}
						}
					}
					visited[nr][nc] = true;
					q.add(new Point(nr,nc));
				}
			}
		return ch;
	}
	static class Point {
		int row,col;
		Point(int r,int c){
			row = r; col = c;
		}
	}
}