[SWEA] 2819: 격자판의 숫자 이어 붙이기(Java)

Yoon Uk·2022년 6월 27일
0

알고리즘 - SWEA

목록 보기
3/3
post-thumbnail

문제

SWEA 2819: 격자판의 숫자 이어 붙이기
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB

풀이

문제 정리

  • 각 격자칸을 기준으로 상하좌우로 움직이며 그 격자에 있는 수를 차례로 붙인다.
  • 방문한 격자를 다시 방문해도 된다.
  • 격자 크기는 4 X 4로 고정되어있다.

문제 접근

  • 각 격자를 방문하며 그 격자에 있는 수를 문자열에 붙여나간다.
    • 7개의 격자값을 DFS를 사용하여 탐색하며 마지막 깊이까지 들어간다.
  • 붙여나간 문자열을 Set에 넣어 중복되는 값은 한 번만 들어가도록 한다.
  • Set에 있는 값들의 수를 출력한다.

코드

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

class Solution
{
    static int[][] map;
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	static HashSet<String> hs; // HashSet을 통해 중복된 값은 자동으로 거른다.
    
	public static void main(String args[]) throws Exception
	{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T;
		T=Integer.parseInt(br.readLine());

		for(int test_case = 1; test_case <= T; test_case++)
		{
            hs = new HashSet<>();
            StringTokenizer st;
            
            map = new int[4][4];
            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++) {
                    move(i, j, 0, ""+map[i][j]);
                }
            }
            System.out.println("#" + test_case + " " + hs.size());
		}
	}
    
    static void move(int x, int y, int depth, String str) { // depth와 HashSet에 넣을 str값을 넘겨준다.
		
		if(depth == 6) { // 첫 격자의 수 제외하고 6개의 격자까지 추가하면 HashSet에 추가하고 종료한다.
			hs.add(str);
			return;
		}
		for(int t=0; t<4; t++) {
			int nx = x + dx[t]; //새로운 격자 좌표
			int ny = y + dy[t]; //새로운 격자 좌표
			
			if(nx >= 0 && ny >= 0 && nx < 4 && ny < 4) { // 격자판 범위 안이면?
            	// 깊이 끝까지 들어가야 하므로 재귀(스택 구조)를 사용한다.
				move(nx, ny, depth + 1, str+map[nx][ny]); // depth값을 +1 해주고 새로운 격자값을 문자열에 붙여준다.
			}
		}
		
	}
}

정리

  • DFS를 사용하여 깊이 끝까지 탐색하며 값을 찾는다.
  • HashSet을 통해 중복된 값을 제거한다.

0개의 댓글