[BOJ 1941] 소문난 칠공주 (Java)

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

1941번: 소문난 칠공주

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main_BOJ_1941 {
	static class Pos{
		int r, c;
		Pos(int r, int c) {
			this.r=r;
			this.c=c;
		}
	}
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	static char[][] map=new char[5][5];
	static boolean[][] check=new boolean[5][5];
	static int answer=0;
	static Pos[] list=new Pos[7];
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		for (int i=0; i<5; i++) {
			String s=br.readLine();
			for (int j = 0; j < 5; j++) {
				map[i][j]=s.charAt(j);
			}
		}
		comb(0, 0, 0, 0);
		System.out.println(answer);

	}
	private static void comb(int start, int count, int sCount, int yCount) {
		if (sCount+(7-count)<4) return;
		int r, c;
		if (count==7) {
			if (isAdjacent()) {
				answer++;
			}
			return;
		}
		for (int i=start; i<25; i++) {
			r=i/5;
			c=i%5;
			if (r<0 || c<0 || r>=5 || c>=5) continue;
			check[r][c]=true;
			list[count]=new Pos(r,c);
			if (map[r][c]=='S') comb(i+1, count+1, sCount+1, yCount);
			else comb(i+1, count+1, sCount, yCount+1);
			check[r][c]=false;
		}
		
	}
	private static boolean isAdjacent() {
		boolean[][] visited=new boolean[5][5];
		visited[list[0].r][list[0].c]=true;
		dfs(list[0].r, list[0].c, visited);
		for (Pos p: list) {
			if (!visited[p.r][p.c]) return false;
		}
		return true;
	}
	
	private static void dfs(int r, int c, boolean[][] visited) {
		for (int i=0; i<4; i++) {
			int nr=r+dr[i];
			int nc=c+dc[i];
			if (nr<0 || nc<0 || nr>=5 || nc>=5) continue;
			if (check[nr][nc] && !visited[nr][nc]) {
				visited[nr][nc]=true;
				dfs(nr, nc, visited);
			}
		}
		
	}

}

 

25개 중에 7개 뽑는 조합의 수를 구해준 뒤, 남은 횟수를 다 S를 뽑아도 S가 4개 이상이 안 나오는 경우는 가지치기 해준다 ((sCount+(7-count)<4) 부분)

 

이 후 7개를 다 뽑았으면 인접한지 체크한다.

첫번째로 뽑은 애를 중심으로 DFS 를 돌린다. 이때 탐색 대상은 경계를 벗어나지 않으면서, 뽑은 자리면서, 아직 방문하지 않은 자리이다. 

DFS가 종료되면 뽑은 애를 기준으로 visited 배열을 체크해서 모두 다 방문했으면 인접했다고 간주하고 answer++ 해주면 된다.

 

 

뽑은 애를 arraylist 이용해서 저장하지 말고,

인접성 단계에서 check[][] 배열을 사용하여 뽑은 첫번째 자리를 기준으로 DFS 돌려주면 메모리를 아낄 수 있다.

사실 이 방법은 BFS 를 쓰면 전역변수인 visitedCnt를 쓰지 않고도 풀 수 있다. 방문할 때마다 cnt++ 해주면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main_BOJ_1941 {
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	static char[][] map=new char[5][5];
	static boolean[][] check=new boolean[5][5];
	static int answer=0;
	static int visitedCount=0;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		for (int i=0; i<5; i++) {
			String s=br.readLine();
			for (int j = 0; j < 5; j++) {
				map[i][j]=s.charAt(j);
			}
		}
		comb(0, 0, 0, 0);
		System.out.println(answer);

	}
	private static void comb(int start, int count, int sCount, int yCount) {
		if (sCount+(7-count)<4) return;
		int r, c;
		if (count==7) {
			if (isAdjacent()) {
				answer++;
			}
			return;
		}
		for (int i=start; i<25; i++) {
			r=i/5;
			c=i%5;
			if (r<0 || c<0 || r>=5 || c>=5) continue;
			check[r][c]=true;
			if (map[r][c]=='S') comb(i+1, count+1, sCount+1, yCount);
			else comb(i+1, count+1, sCount, yCount+1);
			check[r][c]=false;
		}
		
	}
	private static boolean isAdjacent() {
		boolean[][] visited=new boolean[5][5];
		int r=0, c=0;
		for (int i=0; i<5; i++) {
			for (int j=0; j<5; j++) {
				if (check[i][j]) {
					r=i;
					c=j;
					break;
				}
			}
		}
		visited[r][c]=true;
		visitedCount=1;
		dfs(r, c, visited);
		if (visitedCount==7) return true;
		else return false;
	}
	
	private static void dfs(int r, int c, boolean[][] visited) {
		for (int i=0; i<4; i++) {
			int nr=r+dr[i];
			int nc=c+dc[i];
			if (nr<0 || nc<0 || nr>=5 || nc>=5) continue;
			if (check[nr][nc] && !visited[nr][nc]) {
				visited[nr][nc]=true;
				visitedCount++;
				dfs(nr, nc, visited);
			}
		}
		
	}

}