백준 1941 <소문난 칠공주>

문제를 처음 잘못 이해해서 한참 헤맷던 문제! 25명 중에 7명을 고르는 문제다. 

 

그러나 처음 이해했던 방식은 어떤 지점에서 DFS를 이용해서 탐색해서 발생할 수 있는 경우를 고르는 문제인 줄 알았지만 아쉽게도 결과는 실패.

 

이러한 문제는 일반적으로 DFS 또는 BFS로 접근을 하다보니 문제에 접근하기 어려웠던 문제이다.

 

이 예제의 경우에도 이렇게 두가지 방법이 존재할 것이다. 그래서 떠오른 방법은 25개 중 7개를 뽑는 조합 문제인것이다!!

 

그래서 생각해낸 접근방법이 25개 중 7개를 고르는데 "Y" 임도연 파의 개수가 4개와 같거나 크면 실패이기 때문에 이점을 중점으로 조합을 생성했다. 

 

일단 25개의 String을 만들어서 차례대로 글자를 하나씩 넣었다 또한  int 형의 resul 배열을 생성해서 7개의 조합을 넣을 배열을 생성하도록 했다.

 

또한 앞에서 말했던 것과 마찬가지로 count는 Y 즉 상대편의 개수 k는 현재 resul 배열의 위치를 나타내도록 했다.

 

이후로는 한 점을 기준으로 총 칸의 길이를 합쳐 7칸이 맞는지 BFS 너비 우선 탐색을 이용해서 확인을 하도록 했다.

가장 처음 resul [0] 위치를 큐에 넣은 다음 위, 아래, 좌, 우 4방향으로 탐색하도록 했다. 

기존의 map을 이차원 배열로 만들었다면 기존에 사용하던 

 

4방향 탐색을 이용할 수 있었겠지만 일차원 배열로 만들었기 때문에 우치를 고려하는데 어려움이 있었다.

다음에는 기존의 방법으로..  resul을 포인트 배열로 만들고 map을 2차원 배열로 만들면 더 간단하게 생각할 수 있을 것 같다.

 

이렇게 count가 7이 되면 result를 1 추가해주고 조합을 이용해 풀었기 때문에 겹치는 점은 존재하지 않을 것이다.

 

DFS, BFS 쪽으로만 생각하다 보니 문제를 접근하는 것이 어려웠다. 더욱 많은 문제를 풀고 접근해봐야겠다. 

 

전체 코드

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

public class Main {

	static String map[];
	static int resul[], visit[], result;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
		map = new String[25];
		resul = new int[7];
		int start = 0;
		for (int i = 0; i < 5; i++) {
			String s = kb.readLine();
			for (int j = 0; j < 5; j++) {
				map[start] = "";
				map[start++] += s.charAt(j);
			}
		}

				
		go(0, 0, 0);
		System.out.println(result);
	}

	public static void go(int st, int count, int k) {
		if (count == 4) {
			return;
		}
		if (k == 7) {
			visit = new int[7];
			find();
			return;
		}
		for (int i = st; i < 25; i++) {
			resul[k] = i;
			if (map[i].equals("Y")) {
				go(i + 1, count + 1, k + 1);
			} else {
				go(i + 1, count, k + 1);
			}
		}
	}

	public static void find() {
		Queue<Integer> q=new LinkedList<Integer> ();
		q.add(resul[0]);
		visit[0]=1;
		int count=1;
		while(!q.isEmpty()) {
			int nex=q.remove();
			for(int i=0;i<7;i++) {
				if(visit[i]==0) {
					if((resul[i]/5==nex/5)&&(resul[i]-1==nex)||
							(resul[i]/5==nex/5)&&(resul[i]+1==nex)
							||(resul[i]==nex+5)||(resul[i]==nex-5))
					{
						visit[i]=1;
						q.add(resul[i]);
						count++;
					}
				}
			}
		}
		if(count==7) {
			result++;
		}
	}

}