BOJ1941 소문난 칠공주 R *

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

1941번: 소문난 칠공주

7명씩 뽑는 조합 만들기 -> 반복문 또는 재귀문

 

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static int[] students = new int[25];
    public static boolean[] check = new boolean[25];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cnt = 0;
        for (int i = 0; i < 5; i++) {
            String str = sc.next();
            for (int j = 0; j < 5; j++) {
                if (str.charAt(j) == 'S') {
                    students[cnt] = 1;
                }
                else {
                    students[cnt] = 0;
                }
                cnt++;
            }
        }
        int princess = nextCombination(0);
        System.out.println(princess);
    }

    public static boolean isFriend(int a, int b) {
        int diff = Math.abs(a - b);
        int max = Math.max(a, b);

        if (diff == 1 && max % 5 != 0) return true;
        if (diff == 5) return true;

        return false;
    }

    static List<Integer> pick = new ArrayList<>();

    public static int nextCombination(int studentNum) {
        // 7명의 학생을 다 뽑았다면
        if (pick.size() == 7) {
            int cnt = 0;
            // 이다솜파 인원 체크
            for (int i = 0; i < 7; i++) {
                if (students[pick.get(i)] == 1) cnt++;
            }
            // 이다솜파가 4명 미만이라면 조합으로 사용하지 않음
            if (cnt < 4) return 0;

            // DFS 탐색 전 초기화
            for (int i = 0; i < 7; i++) {
                check[i] = false;
            }
            // 7명이 모두 인접해있다면 조합으로 인정함
            if(dfs(0) == 7) return 1;
            return 0;
        }
        // 25명의 학생을 다 순열 생성에 사용했는데, 7명이 모이지 않았다면 종료
        if (studentNum >= 25) return 0;

        int ret = 0; // 조합의 개수
        // studentNum 번째 학생을 포함하지 않는 경우
        ret += nextCombination(studentNum + 1);
        // studentNum 번째 학생을 포함하는 경우
        pick.add(studentNum);
        ret += nextCombination(studentNum + 1);
        pick.remove(pick.size() - 1);
        return ret;
    }

    public static int dfs(int studentNum) {
        int count = 1;
        check[studentNum] = true;
        for (int i = 1; i < 7; i++) {
            int me = pick.get(studentNum);
            int you = pick.get(i);
            if (!check[i] && isFriend(me, you)) {
                count += dfs(i);
            }
        }
        return count;
    }
}

 

아래는 내가 초기에 접근했던 방식 -> 틀림

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

public class Main
{
    
    public static class Node{
        public int c;
        public int r;
        public boolean isS;
        
        Node(int r, int c, boolean isS){
            this.c=c;
            this.r =r;
            this.isS=isS;
        }
        public boolean equals(Node node){
            if(node.c==this.c && node.r==this.r ){
                return true;
            }
            return false;
        }
        public String toString(){
            return "["+r+", "+c +", "+isS+"]";
        }
    }
    
    static String[][] map = new String[5][5];
    static HashSet<HashSet<Node>> ansSet = new HashSet();
    static int[] move_x = new int[]{1,0,-1,0};
    static int[] move_y = new int[]{0,1,0,-1};
    
    public static void dfs(int x, int y,HashSet<Node> tempSet, boolean[][] visited){
        
        if(tempSet.size()==7){
            int count_s = 0;
            for(Node node:tempSet){
                if(node.isS) count_s++;
                
            }
            if(count_s>=4){
                ansSet.add(tempSet);
            }
        }else{
            if(visited[x][y]) {
                return;
            }
            visited[x][y] =true;
            Node node = new Node(x,y,map[x][y].equals("S"));
            tempSet.add(node);
            
            for(int i=0;i<4;i++){
                if(x+move_x[i]>=0 && x+move_x[i]<5 && y+move_y[i]>=0 && y+move_y[i]<5){
                    dfs(x+move_x[i], y+move_y[i], tempSet ,visited);
                }
            }
            
        }
    }
	public static void main(String[] args) throws IOException{
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    
	    for(int i=0;i <5;i++){
	        String[] temp = br.readLine().split("");
	        for(int j=0;j<5;j++){
	            map[i][j] = temp[j];
	        }
	    }
	    
	    for(int i=0;i<1;i++){
	        for(int j=0; j<1;j++){
	            HashSet<Node> tempSet = new HashSet();
	            boolean[][] visited = new boolean[5][5];
	            dfs(i,j,tempSet,visited);
	        }
	    }
	    
	    System.out.println(ansSet);
	    
	    
	}
}