SWEA ) 격자판에 숫자이어붙이기

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB

SW Expert Academy

---

 

map을 돌면서 map에 적힌 숫자를 누적시켜 7 개가되었을때

 

 

 

그러한 string이 몇개 있는지 구하는 문제이다.

 

 

 

DFS를 돌면서 결과를 Hashset안에 넣고 마지막에 Hashset의 크기가 

 

 

 

정답이 되는 문제이다.

 

 

 

사실 문제는 간단했지만 여러 의문점이 남는다.

 

 

 

String의 자료형 타입은 Non-primitive이므로 heap영역에 객체가 생성될텐데

 

 

DFS인자로 넘겨줄때에는 hashcode값 / 즉 객체의 주소값을 넘기면서 map의 값을 누적해가는데

7일때 hashmap에 넣고 끝내도  heap 영역에 남아있지 않을까?

 

그래서 처음에 dfs가 끝나고 다시 map의 위치의 string 값을 빼주는 형식으로 진행했는데 stack overflow가 났다.

(빙글빙글 도는 경우의 수가 계속 생김)

DFS를 돌때 hashcode값

 그래서 궁금해서 hashcode값을 찍어보았다.

보면 DFS를 돌면서 누적되는 String은 하나의 객체가아니고 서로 다른 객체를 생성하면서 

탐색을 진행하는 것을 알 수 있었다. ( 값이 같으면 하나의 객체를 바라본다 )

 

객체지향을 공부하면서 이런부분에서 계속 헷갈리는데..

정리를 확실하게 해야겠다.

---

 
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class 격자판에숫자이어붙이기 {
    static int answer= 0;
    static String map[][] = new String[4][4];
    static HashSet<String> HS = new HashSet<>();
    static int dir[][] = {{1,0},{-1,0},{0,-1},{0,1}};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(st.nextToken());
        for(int tc = 1 ;tc <= t ; tc++) {
            
            for(int y = 0 ; y< 4 ; y++) {
                st = new StringTokenizer(br.readLine());
                for(int x= 0 ; x < 4 ; x++) {
                    map[y][x] = st.nextToken();
                }
            }
            
            for(int y = 0 ; y < 4 ; y++) {
                for(int x = 0; x< 4 ; x++) {
                    DFS(y,x,"");
                }
            }
            answer = HS.size();
            sb.append("#"+tc + " "+answer+"\n");
            answer = 0;
            HS.clear();
        }
        System.out.println(sb);
    
    }
    public static void DFS(int y, int x, String string) {
        if(string.length()==7) {
            HS.add(string);
            return;
        }
        else {
            for(int index = 0 ; index < 4;  index++) {
                int ny = y + dir[index][0];
                int nx = x + dir[index][1];
                if(ny >= 0 && nx >= 0  && ny< 4 && nx < 4) {
                    DFS(ny,nx,string+map[ny][nx]);
                }
            }
        }
        
    }
}