알고리즘 스터디 6월 2주차 문제1 (숫자판 점프)

Jun 12, 2020

Post Series

문제#

링크로 대체

풀이 및 주저리..

오프라인 백준 강의때 풀지 못했던 문제를 다시 풀어보기 위해 돌아왔다!! 첫 시작은 숫자판 점프로 쉽게 구현이 가능한 브루트 포스 문제로 시작했다. 숫자판의 값들을 먼저 int 형 2차원 배열에 값을 넣어주고 하나씩 값을 확인하면서 풀어보았다. 처음에 시간복잡도를 계산해봤을때 25 * 4의 5승으로 시간이 오래걸릴것 같은 문제가 아니여서 브루트포스 문제임을 알아차리는 것과 Set 을 활용해서 중복을 검사하여 처리해보았다.

코드

package baekjoon.algorithm.day03;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class JumpNumberBoard {
    static int[][] map = new int[5][5];
    static Set<String> numberSet = new HashSet<>();
    static final int[] dx = {1, -1, 0, 0}, dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                map[i][j] = scanner.nextInt();
            }
        }

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                go(i, j, 1, String.valueOf(map[i][j]));
            }
        }

        System.out.println(numberSet.size());
    }

    private static void go(int x, int y, int len, String str) {
        if (len == 6) {
            if (!numberSet.contains(str)) {
                numberSet.add(str);
            }
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nX = x + dx[i];
            int nY = y + dy[i];
            if (nX >= 0 && nX < 5 && nY >= 0 && nY < 5) {
                go(nX,nY,len +1,str + map[nX][nY]);
            }
        }
    }
}

기억에 남길 것!

시간 복잡도 계산과 자료구조의 활용