728x90
https://school.programmers.co.kr/learn/courses/30/lessons/1844
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
728x90
메모리: 53.9 MB, 시간: 10.19 ms
사용 알고리즘: BFS
import java.util.*; class Solution { public int solution(int[][] maps) { // maps 크기 int n = maps.length; int m = maps[0].length; // 사방탐색 int[] dx = {-1, 1, 0, 0}; int[] dy = {0, 0, -1, 1}; // (1, 1)에서 출발하여 각 위치의 최단거리를 저장하고 있는 배열 int[][] minLength = new int[n][m]; for(int i = 0; i < n; i++) { // 최대값으로 초기화 Arrays.fill(minLength[i], Integer.MAX_VALUE); } minLength[0][0] = 1; // bfs Queue<int[]> q = new ArrayDeque<>(); q.add(new int[] {0, 0, 1}); int[] now; int nx, ny; int answer = -1; while(!q.isEmpty()) { now = q.poll(); if(now[0] == n - 1 && now[1] == m - 1) { answer = now[2]; break; } for(int i = 0; i < 4; i++) { // 사방탐색 nx = now[0] + dx[i]; ny = now[1] + dy[i]; if(nx >= 0 && nx < n && ny >= 0 && ny < m) { // 범위 탐색 if(maps[nx][ny] == 1 && minLength[nx][ny] > now[2] + 1) { // 벽이 아니고, 최단 거리일 때만 이동 minLength[nx][ny] = now[2] + 1; q.add(new int[] {nx, ny, minLength[nx][ny]}); } } } } return answer; } }
728x90
'Problem Solving > Programmers' 카테고리의 다른 글
[프로그래머스, 42587] 프로세스 (java) (0) | 2024.09.27 |
---|---|
[프로그래머스, 154539] 뒤에 있는 큰 수 찾기 (java) (1) | 2024.09.26 |
[프로그래머스, 131127] 할인 행사 (java) (0) | 2024.09.20 |
[프로그래머스, 42889] 실패율 (java) (1) | 2024.09.12 |
[프로그래머스, 43165] 타겟 넘버 (java) (0) | 2024.09.10 |