오늘 풀어본 문제는
백준 1941번 소문난 칠공주 입니다.

📕 문제 링크

❗️코드

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.regex.Matcher;
import java.util.regex.Pattern;

class Team
{
    String alpha,num;

    public Team(String alpha,String num)
    {
        this.alpha = alpha;
        this.num = num;
    }

}
public class Main {
    static char [] map;
    static int [] move = {-1,-5,5,1};
    static boolean [] isVis;
    static ArrayList<Team> answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        map = new char[25];

        int idxCnt = 0;
        for(int i = 0; i < 5; ++i)
        {
            String tmp = br.readLine();
            for(int j = 0; j < 5; ++j)
            {
                map[idxCnt++] = tmp.charAt(j);
            }
        }
        answer = new ArrayList<>();
        comb(new Team("",""),0);
        int answerCnt = 0;
        for(Team t : answer)
        {
            if(isLinked(t)) answerCnt++;
        }
        System.out.print(answerCnt);
    }
    static void comb(Team tmp, int idx)
    {
        if(tmp.alpha.length() == 7)
        {
            Pattern pattern = Pattern.compile("[S]");
            Matcher matcher = pattern.matcher(tmp.alpha);
            int sCnt = 0;
            while(matcher.find()) sCnt++;
            if(sCnt > 3) answer.add(new Team(tmp.alpha,tmp.num));
            return;
        }
        if(idx == 25) return;

        comb(new Team(tmp.alpha+map[idx],tmp.num+idx+" "),idx+1);
        comb(new Team(tmp.alpha,tmp.num),idx+1);
    }
    static boolean isLinked(Team team)
    {
        boolean [] check = new boolean[25];
        isVis = new boolean[25];
        String [] numbers = team.num.split(" ");
        for(String s : numbers)
        {
            check[Integer.parseInt(s)] = true;
        }

        Queue<String> q = new LinkedList<>();
        q.add(numbers[0]);
        isVis[Integer.parseInt(numbers[0])] = true;

        int cnt = 0;
        while(!q.isEmpty())
        {
            String tmp = q.poll();
            int cur = Integer.parseInt(tmp);
            int end = cur % 5;
            cnt++;
            for(int i = 0; i < 4; ++i)
            {
                if(end == 4)
                {
                    if(i == 3) continue;
                }
                else if(end == 0)
                {
                    if(i == 0) continue;
                }
                int m = cur + move[i];
                if(!isValid(m) || isVis[m] || !check[m]) continue;
                isVis[m] = true;
                q.add(m+"");
            }
        }
        return cnt == 7;
    }
    static boolean isValid(int x)
    {
        return x >= 0 && x < 25;
    }
}

📝 풀이

T 또는 십자 형태의 탐색까지 요구되므로 dfs로는 구현이 쉽지 않아 조합을 이용했습니다. 5*5 형태의 자리에서 7개를 뽑아 조합을 구성한 후, 이들이 서로 연결되어있는지 확인하면 됩니다.
comb의 재귀호출을 통해 조합이 완성되면 S를 몇개 포함하여 조합했는지 확인하고, 4개 이상일 경우만 ArrayList에 담아줍니다.
마지막으로, 연결여부를 확인하여 모두 연결되어있다면 카운트를 올려줍니다.

📜 후기

처음에 dfs로 계속 풀다가 도대체 왜 안되나 싶어 찾아보니, T 또는 십자라는 경우의 수가 있다는 것을 깨달았습니다. 접해보지 못한 문제는 항상 당황스러운 것 같아요..
정답은 한번에 통과했지만 코드가 조금 어거지로 풀어진 느낌이라 자기전에 다른분들 코드를 보고 리뷰 한번 해야겠습니다.ㅋㅋㅋㅋ