글 읽기 - 7공주가 결성하자.

edwardyoon 8년 전 0

헤매다보니 코드가 더럽긴한데, 완전히 모든 경우를 확인하면서 7공주가 결성되었는지 체크합니다.

여러가지 테스트를 해보고 다 맞다고 생각되는데 안넘어가네요.

문제를 잘못읽었는지 .. 어디가 잘못된걸까 지적바랍니다.

public class Main {

  static int[][] map = new int[5][5];
  static int s;

  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);

    s = 0;
    for (int i = 0; i < 5; i++) {
      String a = sc.nextLine();
      for (int j = 0; j < 5; j++) {
        if (a.substring(j, j + 1).equals("Y"))
          map[i][j] = 0;
        else {
          map[i][j] = 1;
          s++;
        }
      }
    }

    String[] list = new String[25 - s];
    int c = 0;
    for (int i = 0; i < 5; i++) {
      for (int j = 0; j < 5; j++) {
        if (map[i][j] == 0) {
          list[c++] = (i + "," + j);
        }
      }
    }

    System.out.println(comb(list, 0, 3, 3, ""));
    sc.close();
  }

  private static int comb(String[] list, int index, int k, int init,
      String prefix) {
    if (k == 0) {
      if (check(prefix, init)) {
        return 1;
      }
    }

    int sum = 0;
    for (int i = index; i < list.length; i++) {
      if (prefix.isEmpty())
        sum += comb(list, i + 1, k - 1, init, prefix + list[i]);
      else
        sum += comb(list, i + 1, k - 1, init, prefix + " " + list[i]);
    }

    return sum;
  }

  static List<String> grouping = new ArrayList<String>();
  
  private static boolean check(String prefix, int init) {
    String[] candidates = prefix.split(" ");

    for (int i = 0; i < init; i++)
      map[Integer.valueOf(candidates[i].split(",")[0])][Integer
          .valueOf(candidates[i].split(",")[1])] = 1;

    String result = isSeven();
    if(!grouping.contains(result)) {
      grouping.add(result);
    } else {
      result = null;
    }
    
    for (int i = 0; i < init; i++)
      map[Integer.valueOf(candidates[i].split(",")[0])][Integer
          .valueOf(candidates[i].split(",")[1])] = 0;

    return (result != null);
  }

  static boolean[][] visited;

  private static String isSeven() {
    visited = new boolean[5][5];

    for (int i = 0; i < 5; i++) {
      for (int j = 0; j < 5; j++) {
        if (map[i][j] == 1 && !visited[i][j]) {
          String x = (go(i, j));
          if(x.split(" ").length == 7) {
            return x;
          }
        }
      }
    }

    return null;
  }

  private static String go(int i, int j) {
    visited[i][j] = true;

    String prefix = i+","+j;
    if (i + 1 < 5 && !visited[i + 1][j] && map[i + 1][j] == 1)
      prefix += " " + go(i + 1, j);
    if (i > 0 && !visited[i - 1][j] && map[i - 1][j] == 1)
      prefix += " " + go(i - 1, j);
    if (j + 1 < 5 && !visited[i][j + 1] && map[i][j + 1] == 1)
      prefix += " " + go(i, j + 1);
    if (j > 0 && !visited[i][j - 1] && map[i][j - 1] == 1)
      prefix += " " + go(i, j - 1);

    return prefix;
  }

}

yukariko 8년 전 0

한 점을 중심으로 탐색하는 방법은 모든 경우를 찾아내지 못합니다.

https://www.acmicpc.net/board/view/5488

이 글을 참고해보세요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

7공주가 결성하자.

edwardyoon 8년 전 0

yukariko 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말