[백준 14940] 쉬운 최단거리 [Java]

백준 14940 - 문제

백준 14940 - 입/출력

---

풀이

각 지점에서 목표지점(2) 까지의 거리를 출력하는 문제로 반대로 생각해서 목표지점에서 출발해 갈 수 있는 모든 거리에 대한 거리를 계산하는 문제로 풀이할 수 있다.

 

입력을 받으면서 목표지점(=출발지점)을 찾으면 0으로 대신 넣어주고, 1이면 -1로 넣어주자.

그 외의 숫자는 그대로 넣어주면 된다.

1일 때 -1을 넣어주는 이유는 출발지점으로부터 출발했을 때 갈수없는 땅(0)으로 둘러싸인 영역은 도달할 수 없는 위치(-1)임을 미리 표시하기 위함이다.

 

출발지점에서 도달할 수 있는 영역의 1들이 전부 -1 로 바뀌면 문제가 없을까?

그렇다, 어차피 도달할 수 있는 영역의 거리들은 이전에 도달한 거리의 값(출발지점 = 0 이므로 0 이상의 수)에 1을 더한 값이기에 결국은 덮어쓰일 것이다.

 

그 이후로는 일반적인 BFS이다.

단, 범위를 벗어났는지 확인하는 과정과 더불어 board[nx][ny]의 값이 0이 아닌지와 이미 방문한적이 없는 곳 인지 판단해주어야 한다.

 

참고로 게시글 작성 기준으로 백준의 채점 언어정보 중 Java의 최상위 버전은 Java 15(JDK 16.0.1, 21-4-20)이지만,

record는 사용할 수 없다.

사실 Point 안만들고 그냥 x + nx처럼 풀어도 된다...

record는 java 14에서 맛보기로 나왔고,

정식지원은 java 16부터 라고 한다.

백준의 Java 컴파일러는 record 정식 릴리즈 직전의 버전이라 컴파일 에러가 뜨는 것 같다.

그게 아니라면 내 정답 돌려줘!!!

---

소스코드

소스코드 보기

---

출처

14940번: 쉬운 최단거리

JEP 395: Records