관리 메뉴

KoreanFoodie's Study

SW 역량테스트 - [모의 SW 역량테스트] 디저트 카페 문제 풀이/해답/코드 (C++ / JAVA) 본문

Data Structures, Algorithm/SW 역량테스트

SW 역량테스트 - [모의 SW 역량테스트] 디저트 카페 문제 풀이/해답/코드 (C++ / JAVA)

hashnut 2020. 9. 29. 11:16


SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 


문제 링크 : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

해답 코드 : 

 

// java
import java.util.ArrayList;
import java.util.Scanner;
import java.io.FileInputStream;
import java.util.Stack;

/*
   사용하는 클래스명이 Solution 이어야 하므로, 가급적 Solution.java 를 사용할 것을 권장합니다.
   이러한 상황에서도 동일하게 java Solution 명령으로 프로그램을 수행해볼 수 있습니다.
 */

class Solution
{
    static int[][] map;
    static int N;
    static boolean[] dest_visit; // < 100
    static boolean[][] visit;
    static int max_dest;

    // for each direction
    static int[] dR = {-1, 1, 1, -1};
    static int[] dC = {1, 1, -1, -1};


    // starting point of each for-loop in main function

    // return opposite direction
    static int op_dir(int x) {
        if (x == 0) return 2;
        else if (x == 1) return 3;
        else if (x == 2) return 0;
        else return 1;
    }

    static boolean isRange(int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= N) {
            return false;
        }
        return true;
    }

    static void clear_visit() {
        for (int i = 0; i < 101; i++) {
            dest_visit[i] = false;
        }
    }

    // draw with dfs
    static void dfs_go(int st_i, int st_j, int next_i, int next_j, int [] dir, int cnt, int cur_dir) {

        // terminator
        if (st_i == next_i && st_j == next_j) {
            max_dest = Math.max(max_dest, cnt);
            return;
        }

        // executor, "i" stands for next direction
        for (int i = 0; i < 4; i++) {

            int temp_i = next_i + dR[i];
            int temp_j = next_j + dC[i];

            // range check
            if (!isRange(temp_i, temp_j)) continue;

            // opposite direction is prohibited
            if (i == op_dir(cur_dir)) continue;

            // if direction is different but has already taken
            if (i != cur_dir && dir[i] > 0) {
                continue;
            }

            // if the rectangle is made, go call dfs_go
            if (temp_i == st_i && temp_j == st_j) {
                dfs_go(st_i, st_j, temp_i, temp_j, dir, cnt, i);
            }

            // if the number is taken already
            if (dest_visit[map[temp_i][temp_j]]) continue;

            dir[i]++;
            dest_visit[map[temp_i][temp_j]] = true;

            dfs_go(st_i, st_j, temp_i, temp_j, dir, cnt+1, i);

            dir[i]--;
            dest_visit[map[temp_i][temp_j]] = false;
        }


    }


    public static void main(String args[]) throws Exception
    {
		/*
		   아래의 메소드 호출은 앞으로 표준 입력(키보드) 대신 input.txt 파일로부터 읽어오겠다는 의미의 코드입니다.
		   여러분이 작성한 코드를 테스트 할 때, 편의를 위해서 input.txt에 입력을 저장한 후,
		   이 코드를 프로그램의 처음 부분에 추가하면 이후 입력을 수행할 때 표준 입력 대신 파일로부터 입력을 받아올 수 있습니다.
		   따라서 테스트를 수행할 때에는 아래 주석을 지우고 이 메소드를 사용하셔도 좋습니다.
		   단, 채점을 위해 코드를 제출하실 때에는 반드시 이 메소드를 지우거나 주석 처리 하셔야 합니다.
		 */
        //System.setIn(new FileInputStream("sample_input.txt"));

		/*
		   표준입력 System.in 으로부터 스캐너를 만들어 데이터를 읽어옵니다.
		 */
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();
		/*
		   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
		*/

        for(int test_case = 1; test_case <= T; test_case++)
        {
            N = sc.nextInt();
            map = new int[N][N];
            dest_visit = new boolean[101];
            max_dest = 0;


            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    map[i][j] = sc.nextInt();
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {

                    int next_i = i + dR[0];
                    int next_j = j + dC[0];

                    // clear dest_visit
                    clear_visit();

                    // range, duplicate check
                    if (!isRange(next_i, next_j)) continue;

                    if (map[i][j] == map[next_i][next_j]) {
                        continue;
                    }

                    // if range is valid, check direction, dessert
                    int[] dir = new int[4];
                    dir[0] = 1; // start from right-down direction

                    dest_visit[map[i][j]] = true;
                    dest_visit[map[next_i][next_j]] = true;

                    dfs_go(i, j, next_i, next_j, dir, 2, 0);

                }
            }

            if (max_dest == 0) max_dest = -1;

            System.out.println("#" + test_case + " " + max_dest);



        }
    }
}

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제

 

0 Comments
댓글쓰기 폼