[PS] 백준 1941 : 소문난 칠공주

문제

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

1941번: 소문난 칠공주

 

해설

 

조금 까다로운 백트래킹 문제 입니다. 문제를 살펴보면 문제에서 주어진 조건은 다음과 같습니다. 

 

1. 총 7명의 학생들로 구성되어야 하며

 

2. S가 항상 4개 이상인 조합으로 구성되어야 한다, 반대로 Y는 항상 3개 이하여야 한다. 

 

3. 강한 결속력을 위해 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.

 

이렇게 보면 일반적인 DFS, 백 트래킹 문제라고 볼 수 있지만 이 문제를 어렵게 하는 요소는 바로 T 자 처럼 중간에 뻗어나아가는 경우도 탐색할 수 있다는 점입니다. 

 

테스트 케이스를 살펴보면 

 

첫번째 처럼 일반적인 DFS 순차 탐색으로 찾아낼 수 있는 경우도 있지만 두번째 경우 처럼 중간에 T 자로 빠져나가서 탐색하는 경우도 고려해야 합니다.

 

어떻게 하면 T 자 형태의 탐색을 수행할 수 있을까요? 이 문제를 푸는 방법은 여러가지가 존재하겠지만 저는 두가지 방법으로 문제를 접근해 보았습니다.

 

1. 문제의 조건을 만족하는 조건의 학생 조합을 찾고, 그 학생 조합이 인접해 있는지 여부를 검사합니다.

 

2. DFS를 수행하되 기존에 방문한 정점들 만이 새로 탐색을 수행할 수 있는 후보군이 될 수 있으므로 이를 고려하여 DFS 백 트래킹으로 문제를 해결합니다.

 

첫번째 방법 같은 경우에는 모든 25개의 정점들에 대해 7개를 선택했을 때 가능한 조합을 먼저 구하고 선택이 모두 끝났을 때 BFS 를 수행하여 해당 정점들이 인접요소 인지 여부를 체크하는 방법입니다.

 

두 번째 방법이 좀 이해하기 난해할 수 있지만 아이디어는 간단합니다. T 자와 같이 탐색을 수행하기 위해서는 기존에 방문했던 정점들에 대해서도 탐색 가능한 정점들을 찾아보아야 합니다. 따라서 백트래킹을 수행하되 기존에 방문한 정점들에 대해 방문 가능한 정점들에 대한 탐색을 수행하면 됩니다.

 

코드를 통해 자세한 구현방법을 살펴보도록 하겠습니다.

 

코드

DFS + BFS

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static char[][] map;
	static boolean[] visit;
	static int total;

	static void dfs(int index, int start, int y) {
		if (index == 7) {
			if (bfs())
				total++;
			return;
		} else {
			for (int i = start; i < 25; i++) {
				if (map[i / 5][i % 5] == 'Y' && y + 1 < 4) {
					visit[i] = true;
					dfs(index + 1, i + 1, y + 1);
					visit[i] = false;
				}
				if (map[i / 5][i % 5] == 'S') {
					visit[i] = true;
					dfs(index + 1, i + 1, y);
					visit[i] = false;
				}
			}
		}
	}

	static class Pair {
		int x, y;

		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
		
	}
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static boolean bfs() {
		Queue<Pair> q = new LinkedList<>();
		boolean[][] check = new boolean[5][5];
		for(int i = 0; i<25; i++) {
			if(visit[i]) {
				check[i / 5][i % 5] = true;
				q.add(new Pair(i / 5, i % 5));
				break;
			}
		}
		int count = 1;
		while(!q.isEmpty()) {
			Pair p = q.poll();
			for(int dir = 0; dir<4; dir++) {
				int nx = p.x + dx[dir];
				int ny = p.y + dy[dir];
				if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
				if(!visit[nx * 5 + ny] || check[nx][ny]) continue;
				check[nx][ny] = true;
				q.add(new Pair(nx, ny));
				count++;
			}
		}
		if(count == 7)
			return true;
		else
			return false;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		map = new char[5][5];
		visit = new boolean[25];
		for (int i = 0; i < 5; i++) {
			String line = br.readLine();
			map[i] = line.toCharArray();
		}
		dfs(0, 0, 0);
		System.out.println(total);
	}
}

 

DFS (백 트래킹) + T자 탐색

package acmicpc.gold;

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

/**
* 알고리즘 : 
*
*/
public class BOJ_1941_소문난_칠공주 {
	static StringBuilder sb = new StringBuilder();
	static int n;
	static int index;
	static char[][] map;
	static boolean[] visit;
	static int ans;
	
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	
	
	static void dfs(int s, int y, int route) {
		if(y > 3 || visit[route]) return;
		
		visit[route] = true;
		if((s + y) == 7) {
			ans += 1;
			return;
		}
		
		for(int i = 0; i< n * n; i++) {
			if((route & (1 << i)) <= 0) continue;
			
			for(int dir = 0; dir<4; dir++) {
				int nx = (i / 5) + dx[dir];
				int ny = (i % 5) + dy[dir];
				
				if(nx < 0 || nx >= n || ny < 0 || ny >= n || (route & (1 << (nx * n + ny))) > 0) continue;
				route |= (1 << (nx * n + ny));
				if(map[nx][ny] == 'S') {
					dfs(s + 1, y, route);
				} else {
					dfs(s, y + 1, route);
				}
				route ^= (1 << (nx * n + ny));
			}
		}
	
	
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = 5;
		map = new char[n][n];
		for(int i = 0; i<n; i++) {
			String line = br.readLine();
			map[i] = line.toCharArray();
		}
		
		visit = new boolean[1 << 25];
		
		for(int i = 0; i<n * n; i++) {
			if(map[i / 5][i % 5] == 'S') {
				dfs(1, 0, (1 << i));
			} else {
				dfs(0, 1, (1 << i));
			}
		}
		System.out.println(ans);
	}
}