SWEA[2819] - 격자판의 숫자 이어 붙이기[D4]

링크

SWEA[2819]

문제설명

• 완전탐색

문제풀이

• 완전탐색

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Solution2819 {
    public static int[][] dir = {    //12시부터 시계방향
            {-1,0},
            {0,1},
            {1,0},
            {0,-1},
    };
    public static int[][] map = new int[4][4];
    public static int N;
    public static int[] index = new int [10000000];
    public static void Search(int r, int c, int cnt, String str) {
        if(cnt==7) {
            index[Integer.parseInt(str)]++;
            return;
        }
        int nr=0;
        int nc=0;
        for (int d = 0; d < 4; d++) {
            nr = r+dir[d][0];
            nc = c+dir[d][1];
            if(nr>=0 && nr<4 && nc>=0 && nc<4) {    //경계안에 있는 경우 이동
                Search(nr,nc, cnt+1, str+map[r][c]);
            }
            else continue;
        }
        //4방향 모두 안되면
        return;
    }
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/swea/2819.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T=Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            int ans = 0;
            int W=0;
            int B=0;
//            입력
            for (int i = 0; i < 4; i++) {
                st = new StringTokenizer(br.readLine()," ");
                for (int j = 0; j < 4; j++) {
                    map[i][j]=Integer.parseInt(st.nextToken());
                }
            }
//            탐색
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    Search(i,j,0,"");
                }
            }

            for (int i = 0; i < 10000000; i++) {
                if(index[i]>0) {
                    ans++;
                    index[i]=0;
                }
            }
            System.out.println("#"+test_case+" "+ans);
            ans=0;
            /*
             * 초기화
             */
        }//end test_case
    }//end main
}

아쉬운점

• 재귀함수 실수
  • 4방향 탐색 시, 탐색도중 막히면 break하면 나머지방향은 탐색안함
  • continue;임
• 코드블록 범위 실수 
  • ans가 선언된 블록이 테스트케이스 블록 밖이라 ans값이 초기화가 안됐음.
• LinkedList써서 contains로 비교하고 size()로 ans값 얻어냈을때는 시간초과뜸
• index[]말고 hashmap(?)쓰는거같던데 봐야알듯.

잘한점

• Index를 이용해서 10000000개 배열을 이용함
• 시간복잡도 구함.
  • O(N) = 16(시작점)*4^7(4방향7칸) = 262144 ... 가능