[백준] 1941 소문난 칠공주 - 조합(Combination) + BFS(너비우선탐색) JAVA

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

1941번: 소문난 칠공주

코드설명

조합과 BFS를 활용합니다.

 

코드의 주요 로직입니다.

1. getCombination 함수는 조합을 통해 7개의 칸을 선택합니다.

2. BFS 함수는 선택된 7개의 칸에 대해 너비 우선 탐색(BFS)을 수행합니다. 시작점으로 선택된 칸에서 상하좌우로 인접한 칸을 탐색하면서 'S'와 'Y'의 개수를 세고, 이미 방문한 곳은 다시 방문하지 않도록 처리합니다.

3. BFS를 통해 탐색한 결과, 선택된 7개의 칸이 모두 연결되어 있고 'S'의 개수가 4개 이상이면 answer 변수를 증가시킵니다.

4. answer 변수는 조건을 만족하는 경우의 수를 저장하며, 이 값이 최종적으로 문제의 답이 됩니다.

 

추가적인 설명으로, 

문제에서각 5*5 에서 방문해야만 하는 조합을 만들어줍니다.

이떄, 7개를 5*5에서 모두 선택했다면, BFS를 통해 선택한 지점의 첫 지점에서부터 Queue를 돌릴 것 입니다.

(이때, 이 문제같은경우 DFS를 사용하는것보다는 BFS를 사용하는 것이 더 좋습니다. 이유는 한 방향으로 갔다가 돌아와서 다시 다른 방향으로도 갈 수 있어야하기 떄문입니다.)

이때 중요한 점은, 우리가 선택한 7개를 모두 순회해야한다는점과 이다솜파('sGroupCnt')가 4개 이상이어야한다는 점입니다.

이를 위해 BFS의 한번의 이동에서 4가지 방향으로 이동할 수 있는 특성을 고려하여 전역적으로 이동한 cnt== 7 로 처리하고, sGroupCnt(이다솜파)의 개수가 4개 이상이어야만 합니다.

만약, BFS가 한번의 큐에서 4가지 이동방향으로 이동할 수 있다는 특성을 무시한다면, 만약 조합이 같은 면을 여러개 마주치는경우에는 올바르게 Count가 안될 것 입니다. ( 처음에 놓쳤던 부분입니다. )

 

이떄 제가 실수했던 부분은, BFS 안에서 아래와 같이 종료조건을 잡았습니다. 이렇게 할경우 만약 BFS의 조합이 서로 1개의 면만 겹친다면 상관없지만 만약 여러면이 겹친다면 4가지 방향으로 Queue가 이동하므로 이미 방문처리가 되어 7 이 될 수 없습니다. 만약 DFS를 통해서 진행했다면 이러한 접근방식이 맞았겠지만, BFS를 통해 진행했기에 밖에서 바라보며 진행해야합니다.

if( (temp.sGroup + temp.yGroup == 7 ) && temp.sGroup >= 4 ) { 여기서 처리할경우 BFS가 이미 방문된곳은 못가므로 모든 경우를 다 돌더라도 합이 7이 안됨
    answer += 1; 
    return ;
}

그러므로, cnt는 조합을 발견할때마다 갱신해주어 7개로 이루어져있는지 확인합니다.

 

이 문제에서 놓쳤었던 점은, simulate에서 r, c는 마지막에 해당 칸을 선택한 칸이 아닌 선택한 칸의 다음 칸이라는 점 입니다. 해당 사항을 놓쳐서 isConnected(r, c)를 보내어, 해당 visited[r][c]가 항상 true로 시작했다고 생각하였는데 틀린 선택이었습니다.

//만약 임도연파가 5명이라면 더 이상 진행하지 않아도 되는점을 이용하기 위해 매개변수로 개수를 세면서 들어간다.
public static void simulate(int level, int r, int c, int countS, int countY) {
    if(c >= 5) {
        r = r + 1;
        c = 0;
    }
    //만약 7공주를 찾았따면, 이다솜파가 적어도 4개 이상이어야합니다.
    if(countS + countY == 7 && countS >= 4) {
        //연결되었는지 확인합니다.
        //처음에 이 부분에서 r, c를 넘겼는데 해당 r,c는 다음 칸을 의미하므로 올바르게 되지 않기에 직접 모두 돌면서 가져오도록 처리합니다.
        if(isConnected() == true) {
            answer += 1;
        }
        return ;
    }
    if(r >= 5) {
        return ;
    }



    //선택하는경우
    visited[r][c] = true;
    if(map[r][c] == 'S') {
        simulate(level + 1, r, c + 1, countS + 1, countY); 
    }else if(map[r][c] == 'Y'){
        simulate(level + 1, r, c + 1, countS, countY + 1);
    }
    visited[r][c] = false;

    //선택하지 않는 경우
    simulate(level + 1, r, c + 1, countS, countY);
}

 

두번째, 삼항연산자는 참/거짓의 결과만 비교가능하다. 삼항연산자는 boolean 형식에서만 사용가능하다.

즉, 아래의 코드는 작동하지 않는다.

map[r][c] ==  'S' ? simulate(level + 1, r, c + 1, countS + 1, countY) : simulate(level + 1, r, c+1, countS, countY + 1);

 

코드

BFS + 조합을 활용한 코드

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

public class Main {
	
	public static int T, N, M;
	public static char[][] map;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static boolean[][] visited;
	public static boolean[][] BFSvisited;
	public static int answer = 0;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	map = new char[5][5];
    	visited = new boolean[5][5];
    	BFSvisited = new boolean[5][5];
    	
    	for(int i=0;i<5;i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		map[i] = st.nextToken().toCharArray();
    	}
    	
    	getCombination(0,0);
    	System.out.println(answer);
	}
	
	public static void getCombination(int level, int idx) {
		if(level == 7) {
			BFS();
			return ;
		}
		for(int i=idx;i<5*5;i++) {
			visited[i/5][i%5] = true;
			getCombination(level + 1, i + 1);
			visited[i/5][i%5] = false;
		}
		
	}
	
	public static void BFS() {
		
		int startX = 0; int startY = 0;
		BFSvisited = new boolean[5][5];
		for(int i=0;i<5;i++) {
			for(int j=0;j<5;j++) {
				if(visited[i][j] == true) {
					BFSvisited[i][j] = true;
					startX = i;
					startY = j;	
				}
			}
		}
		
//		System.out.println("======================");
//		for(int i=0;i<5;i++) {
//			for(int j=0;j<5;j++) {
//				System.out.print(" "+BFSvisited[i][j]);
//			}
//			System.out.println();
//		}
//		
		Queue<Node> q = new LinkedList<>();
		int sGroupTemp = 0;
		if(map[startX][startY] == 'S') {
			q.offer(new Node(startX, startY, 1, 0));
			BFSvisited[startX][startY] =false;
			sGroupTemp = 1;
		}else{
			q.offer(new Node(startX, startY, 0, 1));
			BFSvisited[startX][startY] =false;
		}
		
		int cnt = 1;
		
		while(!q.isEmpty()) {
			Node temp = q.poll();
			
//			if( (temp.sGroup + temp.yGroup == 7 ) && temp.sGroup >= 4 ) { 여기서 처리할경우 BFS가 이미 방문된곳은 못가므로 모든 경우를 다 돌더라도 합이 7이 안됨
//				answer += 1; 
//				return ;
//			}
			
			for(int dir = 0; dir< 4; dir++) {
				int nx = temp.r + dx[dir];
				int ny = temp.c + dy[dir];
				
				if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
				if(BFSvisited[nx][ny] == true) {
					if(map[nx][ny] == 'S') {
						sGroupTemp += 1;
						q.offer(new Node(nx, ny, temp.sGroup + 1, temp.yGroup));	
					}else {
						q.offer(new Node(nx, ny, temp.sGroup, temp.yGroup + 1));
					}
					cnt += 1;
					BFSvisited[nx][ny] = false;
				}
			}
		}
		if(cnt == 7 && sGroupTemp >= 4) { //밖에서 cnt를 처리해야 BFS를 진행하며 모든 경우를 다 체크할 수있다. 
			answer += 1;
		}
		
	}
}

class Node{
	int r;
	int c;
	int sGroup;
	int yGroup;
	public Node(int r, int c, int sGroup, int yGroup) {
		this.r=r;
		this.c=c;
		this.sGroup=sGroup;
		this.yGroup=yGroup;
	}
}

 

DFS로 하려다가 실패코드

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

public class Main {
	
	public static int T, N, M;
	public static char[][] map;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static int[][] DP;
	public static boolean[][] visited;
	public static int answer = 0;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	map = new char[5][5];
    	visited = new boolean[5][5];
    	
    	for(int i=0;i<5;i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		map[i] = st.nextToken().toCharArray();
    	}
    	for(int i=0;i<5;i++) {
    		for(int j=0;j<5;j++) {
    			if(map[i][j] == 'S') {
    				visited[i][j] = true;
        			answer += simulate(1, i, j, 1, 0);
        			visited[i][j] = false;	
    			}else {
    				visited[i][j] = true;
        			answer += simulate(1, i, j, 0, 1);
        			visited[i][j] = false;
    			}
    			
    		}
    	}
    	System.out.println(answer);
    	
	}
	
	public static int simulate(int level, int sX, int sY, int sGroup, int yGroup) {
		if(sGroup >= 4) return 0;
		if(yGroup == 7) return 0;

		if(level == 7) {
			return 1;
		}

		
		int nx = 0, ny = 0;
		int successCnt = 0;
		
		for(int dir = 0; dir<4; dir++) {
			nx = sX + dx[dir]; ny = sY + dy[dir];
			if(nx >= 0 && nx < 5 && ny >= 0 && ny < 5) {
				if(visited[nx][ny] == false) {
					
					visited[nx][ny] = true;
					if(map[nx][ny] == 'S') {
						successCnt += simulate(level + 1, nx, ny, sGroup + 1, yGroup);
					}
					else {
						successCnt += simulate(level + 1, nx, ny, sGroup, yGroup + 1);
					}
					visited[nx][ny] = false;	
				}
			}			
		}
		
		return successCnt;
	}
	
}

 

사실상 첫번째 코드와 비슷하지만, 재귀함수에서 변수가 많이 설정되어 속도가 약 1.8배 이상 느린 코드입니다.

아래 코드처럼, 임도연파와 이다솜파의 숫자를 굳이 가져가지 않아도 되고, 마지막에 BFS에서 선택하는것이 속도를 줄일 수 있는 더 좋은 방법으로 보입니다. 

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

public class Main {
	public static int N, M, K;
	public static char[][] map = new char[5][5];
	public static boolean[][] visited = new boolean[5][5];
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i=0;i<5;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			map[i] = st.nextToken().toCharArray();
		}
		simulate(0, 0, 0, 0, 0);
		System.out.println(answer);
		
	}
	
	//만약 임도연파가 5명이라면 더 이상 진행하지 않아도 되는점을 이용하기 위해 매개변수로 개수를 세면서 들어간다.
	public static void simulate(int level, int r, int c, int countS, int countY) {
		if(c >= 5) {
			r = r + 1;
			c = 0;
		}
		//만약 7공주를 찾았따면, 이다솜파가 적어도 4개 이상이어야합니다.
		if(countS + countY == 7 && countS >= 4) {
			if(isConnected() == true) {
				answer += 1;
			}
			return ;
		}
		if(r >= 5) {
			return ;
		}
		
		//선택하는경우
		visited[r][c] = true;
		if(map[r][c] == 'S') {
			simulate(level + 1, r, c + 1, countS + 1, countY); 
		}else if(map[r][c] == 'Y'){
			simulate(level + 1, r, c + 1, countS, countY + 1);
		}
		visited[r][c] = false;
		
		//선택하지 않는 경우
		simulate(level + 1, r, c + 1, countS, countY);
	}
	
	public static boolean isConnected() {
		Queue<Node> q = new LinkedList<>();
		boolean[][] bfsVisited = new boolean[5][5];
		boolean flag = false;
		for(int i=0;i<5;i++) {
			for(int j=0;j<5;j++) {
				if(visited[i][j] == true) {
					q.offer(new Node(i, j));
					bfsVisited[i][j] = true;
					flag = true;
					break;
				}
			}
			if(flag == true) break;
		}
		
		int count = 1;
		while(!q.isEmpty()) {
			Node temp = q.poll();
			int r = temp.r;
			int c = temp.c;
			if(count == 7) {
				return true;
			}
			
			for(int dir = 0; dir < 4; dir++) {
				int nr = r + dx[dir];
				int nc = c + dy[dir];
				
				if(nr < 0 || nr >= 5 || nc < 0 || nc >= 5) continue;
				if(visited[nr][nc] == false) continue;
				if(bfsVisited[nr][nc] == true) continue;
				bfsVisited[nr][nc] = true;
				q.offer(new Node(nr, nc));
				count += 1;
			}
			
		}
		
		return false;
	}
}


class Node{
	int r;
	int c;
	public Node(int r, int c) {
		this.r=r;
		this.c=c;
	}
}