Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- Design Pattern
- 2156번
- 클린코드
- 가장 긴 증가하는 부분 수열2
- 1300번
- Design Patterns
- 코딩테스트
- 1043번
- 프로그래머스
- Spring
- 10830번
- Dxerr.h
- java
- 백준
- 2206번
- 11758번
- Adapater Pattern
- SerialDate 리펙터링
- 냄새와 휴리스틱
- programmers
- 2166번
- 자바의 정석
- springboot
- BOJ
- 9장
- 코딩 테스트
- 17장
- java의 정석
- DxTrace
- 11286번
Archives
- Today
- Total
Don't give up!
[프로그래머스] 여행경로 (java) 본문
코딩테스트 연습 - 여행경로 | 프로그래머스 (programmers.co.kr)
어떻게 생각하고 문제를 풀었는가?
모든 도시를 방문할 수 있는 여행경로를 구하는 과정에 있어 출발지가 같은 티켓이 존재할 수 있다는 점을 고려하여 그래프 탐색을 진행하고 조건에 맞지 않을 경우 되돌아오는 DFS를 적용하고자 하였습니다.
ICN에서부터 시작하여 출발지 문자열이 일치하는 인덱스를 찾고, 해당 티켓을 사용하였을 경우 모든 경로를 탐색할 수 없다면 다른 티켓을 탐색하는 방식으로 진행한다면 올바른 경로를 찾을 수 있을 것이라고 생각하였습니다.
코드
import java.util.*;
class Solution {
private static final String START = "ICN";
private static LinkedList<String> waypoints = new LinkedList<>();
private boolean[] used;
private String[][] tickets;
public String[] solution(String[][] tickets) {
setTickets(tickets);
used = new boolean[tickets.length];
Arrays.sort(tickets, (x,y) -> x[1].compareTo(y[1]));
waypoints.add(START);
searchPath(START,0);
return waypoints.toArray(new String[0]);
}
private boolean searchPath(String start, int count){
if(count == tickets.length) return true;
for(int i=0; i<tickets.length; i++){
if(!used[i] && start.equals(tickets[i][0])){
used[i] = true;
waypoints.add(tickets[i][1]);
boolean isCorrect = searchPath(tickets[i][1], count+1);
if(isCorrect) return true;
used[i] = false;
waypoints.removeLast();
}
}
return false;
}
private void setTickets(String[][] tickets){
this.tickets = tickets;
}
}
LinkedList를 사용하여 DFS를 구현하였습니다.
String 배열 tickets의 첫번째 원소와 출발지 문자열이 일치할 경우 LinkedList에 추가한 후 그래프 탐색을 계속 진행하고, 모든 도시를 방문할 수 없는 경우 이전 상태로 복구하여 다음 출발지를 모색합니다.
LinkedList로 DFS를 구현함에 있어 주의해야 할 점은 LinkedList의 pop, remove, poll함수는 첫번째 원소를 제거한다는 점입니다.
이전 상태로 복구하기 위해서는 remove, poll이 아닌 removeLast, pollLast 함수를 사용하여야 합니다.
'Coding Test > Programmers' 카테고리의 다른 글
[프로그래머스] 기둥과 보 설치 (java) (0) | 2021.08.29 |
---|---|
[프로그래머스] 셔틀버스 (java) (0) | 2021.07.17 |
[프로그래머스] 표 편집 (java) (0) | 2021.07.13 |