[프로그래머스] 여행경로(Level 3)

📝문제 링크

프로그래머스 > 깊이/너비 우선 탐색 > 여행경로 문제보기

🔑문제 KeyPoint

🎨예제를 보고 그림을 그려 이해해보자!
DFS나 BFS탐색은 그림으로 이해를 하는것이 큰 도움이 되는 것 같다

예제2번을 기준으로 그래프를 방문순서대로 표시하였다.

해당 문제는 Level로 트리로 접근을 어떻게 해야할지 도저히 감이 오지 않았다.
그래서 그림을 그려보니, 💇‍♀️정점을 2번 방문할 수 있도록 체크하는 것이 포인트였다.

그래서 이 문제를 접근하려면 2가지를 알아야 한다.
1. 종료조건은 방문한 카운트수와 tickets.length가 같아지는 경우이다.
2. 같은 방문지를 2번 방문할 수 있도록 해줘야 한다.

💻문제 풀이

처음에는 dfs 함수안의 매개변수 String route 을 사용하여, 방문한 루트를 계속 넘겨주려고 하였다.

public void dfs(String[][] tickets, String departure, String route, int count) {
	if(count == tickets.length) {
		list.add(routes);
		return;
	}
	for(int i=0; i<tickets.length; i++) {
		if(tickets[i][0].equals(departure)  && !visited[i]) {
			visited[i]=true;
			route += ","+departure ;
			dfs(tickets, tickets[i][1], route, count+1 );
			// 같은 방문지가 있는 경우, 다른 방문지를 돌기위해 false로 설정
			visited[i]=false;

		}
	}
}

그런데, 같은 방문지를 2번 돌려면 함수내에서 사용하는 것이 불가능하다.
ATL의 경우, 두 가지의 방문지 ICN, SFO가 존재하는데 위의 경우처럼 route를 함수내에서 쓰는 변수로 설정해버리면 이렇게 중복되는 결과 값이 나와버린다.

구팀장님의 찬스를 통해, 다른 블로그를 참조했다.
다른 답을 보고도 이해하는데 꽤 오랜 시간이 걸린 문제이다.💆‍♀️

routes를 전역변수로 이용하여 처리하기
위에서 발견한 중복 방문지를 제거해주기 위해 routes=routes.substring(0, routes.length()-4);로 해당 공항을 방문하지 않았던 것 처럼 routes를 처리하면 된다.

boolean[] visited ;				// 방문여부 체크
List<String> list = new ArrayList<String>();	// 경로들을 담을 리스트
String routes = "";				// 경로를 표시할 전역변수

public String[] solution(String[][] tickets) {
	String[] answers = new String[tickets.length+1];
	visited = new boolean[tickets.length];
	answers = new String[tickets.length+1];
	
	for(int i=0;i<tickets.length;i++) {
		if(tickets[i][0].equals("ICN")) {
       			// 방문여부를 체크해주고,
			visited[i]=true;
			routes ="ICN";
			dfs(tickets, tickets[i][1],"ICN",1);
           		// false로 체크하는 이유는 , 
               		// ICN으로 시작하는 다른 정점을 후에 방문하기 위함이다.
			visited[i]=false;		
		}
	}
    	// 알파벳 순서대로 정렬
	Collections.sort(list);
	answers = list.get(0).split(",");
	return answers;
}


public void dfs(String[][] tickets, String departure, int count) {
	// 출발지를 경로에 추가
	routes +=","+departure;
	if(count == tickets.length) {
		list.add(routes);
		return;
	}
	for(int i=0; i<tickets.length; i++) {
		if(tickets[i][0].equals(departure)  && !visited[i]) {
			visited[i]=true;
			dfs(tickets, tickets[i][1], count+1 );
			
			// 같은 방문지가 있는 경우, 다른 방문지를 돌기위해 false로 설정
			// 그리고 routes에서도 지워주기 위해 subString(0, length-4)으로 설정 
			visited[i]=false;
			routes = routes.substring(0, routes.length()-4);
		}
	}
}

전체 소스 보기

참고 블로그
DFS programmers 프로그래머스 자바 ‘여행경로’ 문제풀이