[Java] 백준 1941번 : 소문난 칠공주*

1. 문제

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

1941번: 소문난 칠공주

 

 

 

2. 풀이 과정

한 장소에서 여러 곳으로 뻗어나갈 수 있기 때문에, 단순 dfs나 bfs로는 풀리지 않는다.

한 장소에 방문하면, 지금까지 방문한 장소를 모두 고려해 갈 수 있는 장소를 탐색한다.

방문한 장소를 찾아서 4방위 탐색해서 dfs로 들어가면 된다.

+) 중복 방지를 위해 visited 배열을 사용한다. 비트마스킹으로 경로 방문 체크를 한다.

import java.io.*;

public class Boj1941 {
	static int result;
	static char map[][];
	static boolean visited[];
	
	public static void dfs(int cnt, int yeon, int v) {
		int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
		if(yeon>3) { return;}
		if(cnt==7) {
			result++;
			return;
		}
		for(int i=0; i<25; i++) {
			if((v&(1<<i))==0) {continue;} //방문 안한건 pass
			int x = i/5;
			int y = i%5;
			for(int j=0; j<4; j++) {
				int nx = x+dx[j];
				int ny = y+dy[j];
				if(0<=nx && nx<5 && 0<=ny && ny<5 && !visited[v|(1<<(nx*5+ny))]) {
					visited[v|(1<<(nx*5+ny))]=true;
					if(map[nx][ny]=='Y') {
						dfs(cnt+1, yeon+1, v|(1<<(nx*5+ny)));
					}
					else {
						dfs(cnt+1, yeon, v|(1<<(nx*5+ny)));
					}
				}
			}
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		map = new char[5][5];
		visited = new boolean[1<<25];
		for(int i=0; i<5; i++) {
			String s = br.readLine();
			for(int j=0; j<5; j++) {
				map[i][j] = s.charAt(j);
			}
		}
		
		for(int i=0; i<5; i++) {
			for(int j=0;j<5; j++) {
				if(map[i][j]=='S') {
					dfs(1, 0, 1<<(i*5+j));
				}
			}
		}
		System.out.println(result);
	}

}

 

결과