매일 Algorithm

프로그래머스 (게임 맵 최단거리)

import java.util.LinkedList;
import java.util.Queue;

public class problem488 {
    class Solution {
        int[] dx = {0, -1, 0, 1};
        int[] dy = {1, 0, -1, 0};

        public int solution(int[][] maps) {
            int answer = 0;
            int[][] visit = new int[maps.length][maps[0].length];

            visit[0][0] = 1; // 시작위치 방문 처리

            // bfs 탐색 시작
            bfs(maps, visit);

            // 가장 빠른길 저장
            answer = visit[maps.length - 1][maps[0].length - 1];

            // 진영에 도착하지 못하는 경우
            if (answer == 0) {
                answer = -1;
            }
            return answer;
        }

        private void bfs(int[][] maps, int[][] visit) {
            Queue<int[]> queue = new LinkedList<>();
            queue.add(new int[]{0, 0}); // 초기값 

            while (!queue.isEmpty()) {
                int[] now = queue.poll();
                int x = now[0]; // x 좌표
                int y = now[1]; // y 좌표

                for (int i = 0; i < 4; i++) {
                    // 4방향 이동 위치 할당
                    int mx = x + dx[i];
                    int my = y + dy[i];

                    // 범위 검증, 방문했는지 검증, 노드에 값이 있는지 확인
                    if (mx >= 0 && mx < maps.length && 
                    	my >= 0 && my < maps[0].length &&
                            visit[mx][my] == 0 && maps[mx][my] == 1) {
                        
                        // 방문 처리, 경우의 값 누적
                        visit[mx][my] = visit[x][y] + 1; 
                        queue.add(new int[]{mx, my});
                    }
                }
            }
        }
    }
}

백준 11048번

import java.util.Scanner;

public class problem489 {
    static int n;
    static int m;
    static int[][] graph;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();

        // (1,1) 부터 시작함으로 배열 크기 할당
        graph = new int[n + 1][m + 1];

        /* 입력
           0 0 0 0 0
           0 1 2 3 4
           0 0 0 0 5
           0 9 8 7 6
         */
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                graph[i][j] = in.nextInt();
                // 왼쪽, 위쪽, 왼쪽 대각선의 최대값을 해야 Index 에러가 발생 X
                graph[i][j] += Math.max(graph[i][j - 1], 
                        Math.max(graph[i - 1][j], graph[i - 1][j - 1]));
            }
        }
        System.out.println(graph[n][m]);
    }
}