[BaekJoon] 1941번 소문난 칠공주 (Java) 문제 풀이 [Gold 3]

문제

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

 

어떻게 풀 것인가?

이 문제는 백트래킹(Backtracking) 을 이용해서 풀었다.

우선 문제를 잘 읽어보면 배열의 크기와 조건이 크지 않음을 알 수 있다.
즉, 브루트포스(완전 탐색) 및 백트래킹을 사용해도 시간 초과 없이 해결할 수 있다.

따라서, 25명 중 7명을 선택하는 조합(combination)을 수행한 후,

• 선택된 7명이 서로 연결되어 있는지 확인하고,
• 최소 4명이 ‘이다솜파’(S)인지 확인하는 방식으로 접근했다.

 

풀면서 놓쳤던점

DFS 탐색 방식의 오류

• 단순히 DFS로 인접한 학생을 탐색하는 것이 아니라, 25명 중 7명을 조합으로 선택한 후, 그 7명이 하나의 연결된 그룹인지 확인해야 했다.
• 즉, DFS로 직접 7명을 선택하면 모든 경우의 수를 탐색하지 못하게 됨.

연결성 체크 로직 누락

• 7명을 선택한 후, 서로 연결되어 있는지 확인하는 과정이 필요했다.
• 따라서 BFS 또는 DFS를 활용해 선택된 7명의 인접 여부를 검사해야 했다.

시간 복잡도 고려

• 25명 중 7명을 선택하는 경우의 수는 25C7 = 480700으로 충분히 탐색 가능하다.
• 이후 BFS 탐색이 최대 7번만 이루어지므로 시간 복잡도는 O(480700 * 7) = O(10^6) 정도로 적절하다

 

이 문제를 통해 얻어갈 것

• 백트래킹과 조합을 활용한 문제 해결 능력
  • 25명 중 7명을 선택하는 조합을 먼저 수행한 후, 유효성을 검사하는 방식
• BFS를 활용한 연결성 검사 기법
  • 선택된 7명이 서로 연결되어 있는지 BFS로 확인
• 탐색 최적화
  • 백트래킹을 이용해 필요 없는 탐색을 줄이는 법 익히기

 

내 코드 

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

public class Main {
	static char[][] map = new char[5][5];
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { 1, -1, 0, 0 };
	static List<int[]> students = new ArrayList<>();
	static int result = 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 line = br.readLine();
			for (int j = 0; j < 5; j++) {
				map[i][j] = line.charAt(j);
				students.add(new int[] { i, j });
			}
		}


		combination(0, 0, new ArrayList<>());
		System.out.println(result);
	}

	static void combination(int start, int depth, List<int[]> selected) {
		if (depth == 7) {
			if (isValid(selected)) {
				result++;
			}
			return;
		}

		for (int i = start; i < 25; i++) {
			selected.add(students.get(i));
			combination(i + 1, depth + 1, selected);
			selected.remove(selected.size() - 1);
		}
	}


	static boolean isValid(List<int[]> selected) {
		
		Queue<int[]> queue = new LinkedList<>();
		boolean[][] visited = new boolean[5][5];

		queue.add(selected.get(0));
		visited[selected.get(0)[0]][selected.get(0)[1]] = true;

		int connectedCount = 1;
		int sCount = map[selected.get(0)[0]][selected.get(0)[1]] == 'S' ? 1 : 0;

		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int x = cur[0], y = cur[1];

			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];

				if (range(nx, ny) && !visited[nx][ny]) {
					for (int[] student : selected) {
						if (student[0] == nx && student[1] == ny) {
							queue.add(new int[] { nx, ny });
							visited[nx][ny] = true;
							connectedCount++;

							if (map[nx][ny] == 'S') {
								sCount++;
							}
						}
					}
				}
			}
		}

		return connectedCount == 7 && sCount >= 4;
	}

	static boolean range(int x, int y) {
		return x >= 0 && x < 5 && y >= 0 && y < 5;
	}
}

• 입력 처리 (BufferedReader)
  • 5×5의 학생 배열을 입력받고, 학생들의 좌표를 students 리스트에 저장.
• 백트래킹을 이용한 조합 탐색 (combination())
  • combination(0, 0, new ArrayList<>()) 호출하여 25명 중 7명을 선택.
  • 선택된 7명의 연결성을 확인 후 result 값 증가.
• BFS를 이용한 연결성 확인 (isValid())
  • queue와 visited 배열을 사용해 7명이 인접한지 확인.
  • S의 개수가 4개 이상인지 체크.
• 출력 (System.out.println(result);)
  • 모든 경우를 탐색한 후, 정답을 출력.

 

참고

X