1189_컴백 홈

사용 알고리즘: bfs,백트래킹

사용 언어: java

 

package week11;

import java.io.*;
import java.util.*;

public class Main_bj_1189_컴백홈 {
	static int r,c,k, ans;
	static char[][] map;
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		map = new char[r][c];
		
		for (int i = 0; i < r; i++) {
			String s = br.readLine();
			for (int j = 0; j < c; j++) {
				map[i][j] = s.charAt(j);
			}
		}
//		for(int i = 0; i < r; i++) System.out.println(Arrays.toString(map[i]));
		//
		
		bfs_1189();
		System.out.println(ans);
	}

	private static void bfs_1189() {
		Queue<Hansu> q = new ArrayDeque<>();
		boolean[][] visit = new boolean[r][c];
		visit[r-1][0] = true;
		q.add(new Hansu(r-1, 0, visit, 1));
		
		while(!q.isEmpty()) {
			Hansu hansu = q.poll();
			
			if(hansu.x == 0 && hansu.y == c-1) {
				if(hansu.move == k) ans++;
				continue;
			}
			
			if(hansu.move > k) continue;
			
			for(int d=0; d<4; d++) {
				int nx = hansu.x + dx[d];
				int ny = hansu.y + dy[d];
				
				if(nx>=0&&nx<r && ny>=0&&ny<c) {
					if(map[nx][ny] != 'T' && !hansu.visit[nx][ny]) {
						boolean[][] newVisit = copyVisit(hansu.visit);
						newVisit[nx][ny] = true;
						q.add(new Hansu(nx, ny, newVisit, hansu.move+1));
					}
				}
			}
		}
	}

	private static boolean[][] copyVisit(boolean[][] visit) {
		boolean[][] tmp = new boolean[r][c];
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				tmp[i][j] = visit[i][j];
			}
		}
		
		return tmp;
	}

}

class Hansu {
	int x;
	int y;
	boolean[][] visit;
	int move;
	
	public Hansu(int x,int y, boolean[][] visit, int move) {
		this.x = x;
		this.y = y;
		this.visit = visit;
		this.move = move;
	}
}

 

오랜만에 풀었다고 한참 걸린 거 실화?