[프로그래머스][DFS] 여행경로(201008)

1. 문제 설명 

programmers.co.kr/learn/courses/30/lessons/43164

코딩테스트 연습 - 여행경로

 

 

1. 문제 설명 

 

 

문제 설명

버스정류장 N개가 있습니다. 각 정류장에는 1번부터 N번까지의 번호가 매겨져 있습니다. 2차원 배열로 주어진 정류장 표지판(signs)에는 A번 정류장에서 B번 정류장으로 가는 버스가 있다면 1, 없다면 0으로 표시되어 있습니다.

예를 들어, 3개의 버스정류장이 있을 때

로 표시된 정류장 표지판이 주어진다면,

• 1번 정류장에서 2번 정류장으로 갈 수 있습니다. (A=1, B=2)
• 2번 정류장에서 3번 정류장으로 갈 수 있습니다. (A=2, B=3)
• 3번 정류장에서 1번 정류장으로 갈 수 있습니다. (A=3, B=1)

또한, 버스를 갈아타는 것이 가능합니다. 예를 들어, 위 예시에서는 1번에서 2번 정류장으로, 그리고 2번에서 3번 정류장으로 가는 버스가 있으므로, 한 번 갈아타서 1번에서 3번 정류장으로 갈 수 있습니다. 버스는 여러번 갈아타는 것이 가능합니다.

우리는 이 표를 이용해서 특정 정류장 A에서 특정 정류장 B로 갈 수 있는지 판단하여, 갈 수 있으면 1, 갈 수 없으면 0으로 표시하려고 합니다.

위 예시에서는

이 되며. A번째 줄의 B번째 숫자는 A 정류장에서 B 정류장으로 갈 수 있는 지의 정보를 나타냅니다. 단, 출발지와 목적지 사이에서 적어도 하나의 버스를 타는 경우에만 1로 표시합니다.

정류장 표지판(signs)이 매개변수로 주어질 때, 특정 정류장 A에서 특정 정류장 B로 도달할 수 있는지를 표시하여 return 하는 solution 함수를 완성해 주세요. 위 예시의 경우는 [[1,1,1],[1,1,1],[1,1,1]]로 return 하면 됩니다.

제한사항

• N : 100 이하의 자연수
• 정류장 표지판(signs)는 2차원 배열이며, 1 또는 0으로만 이루어져 있습니다. 단, i번째 줄의 i번째 숫자는 항상 0입니다.

---

입출력 예

nsignsanswer

3	[[0,1,0],[0,0,1],[1,0,0]]	[[1,1,1],[1,1,1],[1,1,1]]
3	[[0,0,1],[0,0,1],[0,1,0]]	[[0,1,1],[0,1,1],[0,1,1]]

입출력 예 설명

 

입출력 예 #1
문제의 예시와 같습니다.

 

입출력 예 #2

• 1번 정류장->3번 정류장->2번 정류장으로 갈 수 있으므로, 1행은 [0,1,1]이 됩니다.
• 2번 정류장->3번 정류장->2번 정류장으로 갈 수 있으므로, 2행은 [0,1,1]이 됩니다.
• 3번 정류장->2번 정류장->3번 정류장으로 갈 수 있으므로, 3행은 [0,1,1]이 됩니다.

 

2. 풀이 

 

1) 나의 화려한 오답 

def solution(n, signs):

    ans_matrix = [[0] * n for i in range(n)]

    # 1. 행마다 탐색
    for row in range(n):
        move_row = []
        ans_matrix = dfs(row, move_row, signs, ans_matrix)

    return ans_matrix

def dfs(row, move_row, signs, ans_matrix):

    # 2. 입력된 행의 열을 하나씩 탐
    move_row.append(row)       # 현재 지점 발자취로 남겨두기
    for col in range(len(ans_matrix)):
        if signs[row][col] == 0 or row == col or col in move_row: # 이미 연결 안되어있거나, 같거나, 거쳐온 출발점이라면,
            continue

        ans_matrix = dfs(col, move_row, signs, ans_matrix)
        
        for b_row in set(move_row[1:]): # 모든 거쳐온 지점들 처음 출발지점과 매칭
        	ans_matrix[move_row[0]][b_row] = 1
                
    return ans_matrix

 

 

구체적으로 어디서 잘못된거인지는 모르겠지만, 

맨 마지막 모든 거쳐온 지점을 처음 출발지점이랑 매칭하는 때에서 잘못된거 같다. 

 

 

 

2) 수정  + 정답 

그래서 solution에서 출발지점을 하나씩  탐색하고 (a)

DFS 에서 a와 연결된 모든 경로(b,c,d) 를 담아 반환하고 

다시 solution 에서 출발지점이었던 (a) 와 (b,c,d)를 전부 이어주는 것 !!!

 

def solution(n, signs):

    ans_matrix = [[0] * n for i in range(n)]

    # 1. 행마다 탐색
    for row in range(n):
        move_row = set() # 2. 아래의 함수에서 나오는 row 연결지점 다 여기 담김
        ans_matrix = dfs(row, move_row, signs, ans_matrix)
        
         # row와 연결지점 다 연결연결
        for next in move_row:
            ans_matrix[row][next] = 1

    return ans_matrix

def dfs(row, move_row, signs, ans_matrix):

    # 3. 입력된 행의 열을 하나씩 탐
    for col in range(len(ans_matrix)):
    	# 이미 연결되었거나, 가세로 같거나, 거쳐온 출발점이라면 다음 지점으로 넘어가
        if signs[row][col] == 0 or row == col or col in move_row: 
            continue

		# 아니면, 연결지점으로 담아두기 
        move_row.add(col)
        
        # 해당 연결 지점으로 다시 탐색!~~~~
        ans_matrix = dfs(col, move_row, signs, ans_matrix)

    return ans_matrix

 

 

*** 유사 문제와의 비교 

 

DFS 전형적인 문제 

 

huidea.tistory.com/99

[프로그래머스][DFS] N-queen (201008)

 

해당 문제에서 구조는 

1) solution : 각 행 탐색 시작 / DFS 결과 담아둘 저장set 생성

2) DFS : 탈출조건 설정 / 재귀식 탐색 타고타고 들어가기 / 3) 타고들어가다 막혔을때 앞에꺼 취소하는 코드 

였고 

 

 

여기 문제에서는

1) solution : 각행마다 탐색 시작 / 이때 DFS 결과 담아둘 저장set 생성

2) DFS : 재귀식으로 탐색 후 해당 결과 다시 solution으로 반환

 

 

3. 정리 

결국 DFS 컨셉은 

 

1) def1 : 탐색 조건 설정 (가로 인덱스 설정) / 모든 경로 저장공간 만들기 

2) def2 : (해당 가로 인덱스의 모든 세로 탐색) --> 조건 충족

      해당 세로 를 다시 가로로 지정하여 def2 재귀                          ===> 이 때 방문 지점  모두 def1 의 공간에 저장 

      만약 탐색을 철회해야하는 조건도 있다면 (Nqueen 과 같이)

      재귀 식 뒤에 remove 조건 달아주기 

 

오히려 이 문제가 더 쉬운거 같기도하다. nqueen은 철회까지 해야하는거라...