배달 [프로그래머스]

문제 풀이 설명

그래프 보자마자 음 이건 dfs 문제군 이라고 감이 왔다.

확실히 예전보다는 문제를 많이 풀어봐서 감을 익힌듯 하다.

 

그래프 그림을 보면 주의 할 점이 보이는데, cycle 이 존재한다는 점이다.

연결된 node를 따라갈때, recursive 하게 함수를 짜게 되는데, 끝이 없다면 stack overflow로 에러가 날수 있다.

그래서 visited 라는 배열을 만들어 이전에 방문한 node에 대해 체크할 수 있도록 구현했다.

 

우선 road 매트릭스를 만들어 준다.

매트릭스 mat[i][j] 는 i번째 마을과 j 번째 마을의 road 길이로 세팅해준다.

각 마을 별로 방문했는지 여부를 알 수 있게 visited 리스트 역시 만들어준다.

mat = []
for i in range(N): #N개의 town 
    temp = []
    for j in range(N):
        if i == j: #1번 마을과 1번 마을간의 거리는 0
            temp.append(0)
        else: 
            temp.append(None)
    mat.append(temp)

for info in road: # 마을간 거리가 담긴 road 리스트 순회
    start = info[0]
    end = info[1]
    dist = info[2]
    if mat[start-1][end-1] != None: # 매트릭스에 이미 거리 정보가 있다면
        if mat[start-1][end-1] > dist: # 더 짧은 길을 택해서 집어 넣어준다.
            mat[start-1][end-1] = dist
            mat[end-1][start-1] = dist
    else: # 매트릭스에 거리 정보가 세팅된적이 없다면
        mat[start-1][end-1] = dist
        mat[end-1][start-1] = dist
# 방문여부 체크
visited = [None] * N

 

이제 그럼 dfs 함수를 만들어야 하는데, 인자는 다음과 같이 설정한다.

• start = 현재 node
• distance = 현재 가능한 거리 (초기는 K), dfs 호출시 distance는 점점 짧아진다.
• mat = 마을간 거리 매트릭스
• visited = 방문 정보

dfs(start = 1, distance= K, mat = mat, visited = visited)

 

dfs 함수는 이렇다

def dfs(start = None, distance = None, mat = None, visited = None):
    if distance < 0: # 넘어온 distance가 혹시 0보다 작다면 도달 불가!
        return None
        
    node_list = [] # 다음 넘어갈 마을을 담을 리스트 생성
    for i, dist in enumerate(mat[start-1]):
        if dist == None: # 거리 정보가 없다면 continue
            continue
        else: #거리 정보가 있다면
            if distance - dist >= 0: # 넘어온 거리에서 현재 거리를 빼준다.
                if visited[i] == None: # 만약 방문 기록이 이제껏 없었다면,
                    node_list.append(i+1) # 다음 넘어갈 마을을 추가
                    visited[i] = distance - dist # 방문 정보 업데이트
                else: # 방문 기록이 있다면!
			#방문했을때 보다 거리차이가 크다면 업데이트, 다음마을 추가
			# ex. distance - dist = 4 이고, 1->1 이면 distance = 4
			# ex. distance - dist = 2 이고, 2->1 이면 4 > 2 이므로 다음마을 추가 x
                    if distance - dist > visited[i]: 
                        node_list.append(i+1)
                        visited[i] = distance - dist
    
    if len(node_list) > 0: # 다음 방문할 마을이 존재한다면
        for node in node_list: # 다음 마을에 대해
						# 거리 정보가 존재하고, 자기 자신이 아닐때(거리가 0이면 자기자신)
            if mat[start-1][node-1] != None and mat[start-1][node-1] != 0:
                dist = distance - mat[start-1][node-1]
                dfs(start = node, distance = dist, mat = mat, visited = visited)
    else:
        return None

    return None

 

내가 헤맸던 부분은 이부분이다.

else: #거리 정보가 있다면
  if distance - dist >= 0: # 넘어온 거리에서 현재 거리를 빼준다.
      if visited[i] == None: # 만약 방문 기록이 이제껏 없었다면,
          node_list.append(i+1) # 다음 넘어갈 마을을 추가
          visited[i] = distance - dist # 방문 정보 업데이트
      else: # 방문 기록이 있다면!
	#방문했을때 보다 거리차이가 크다면 업데이트, 다음마을 추가
	# ex. distance - dist = 4 이고, 1->1 이면 distance = 4
	# ex. distance - dist = 2 이고, 2->1 이면 4 > 2 이므로 다음마을 추가 x
          if distance - dist > visited[i]: 
              node_list.append(i+1)
              visited[i] = distance - dist

방문 기록이 존재할때는 다음 방문 마을에 추가하지 않게끔 (cycle에 타지 않게끔 하기 위해) 짰더니, 성공하지 못했다. 그럼 방문기록이 있더라도 다음 마을을 위해 방문해야 하는 경우가 있다는 말이다.

 

여러번 수정하면서 깨달은건,

거리가 짧으면 이전 거리에서 뺄 숫자가 작다는 말이고,

해당 값으로 방문 기록을 삼으면 해당 기록보다 짧은 거리에 한해서만 방문할 터 이니

중복 방문도 막을 수 있을 터 였다.

 

해당 이미지를 봐보자.

• 1 번 마을에서는 다음 방문 마을 후보로 [1,2,3] 을 추가 한다. (1번 마을은 거리가 0이기 때문에 순회 제외)
• 2 번 마을에서는 다음 방문 마을 후보로 [1, 3] 을 추가 한다. 이때, 1번에서 넘어올때 거리가 빠져 현재 남은 거리는 2 (4 - 2) 그 상황에서 2 → 1 일 경우, visited[0] = 4 보다 거리가 작기 때문에 다음 방문 마을 후보에서 제외 가능!

해당 로직으로 진행한 결과는 다음과 같다.

 

전체 코드는 아래와 같다.

def dfs(start = None, distance = None, mat = None, visited = None):
    if distance < 0:
        return None
        
    node_list = []
    for i, dist in enumerate(mat[start-1]):
        if dist == None:
            continue
        else:
            if distance - dist >= 0:
                if visited[i] == None:
                    node_list.append(i+1)
                    visited[i] = distance - dist
                else:
                    if distance - dist > visited[i]:
                        node_list.append(i+1)
                        visited[i] = distance - dist
    # print(start, node_list, visited)
    if len(node_list) > 0:
        for node in node_list:
            if mat[start-1][node-1] != None and mat[start-1][node-1] != 0:
                dist = distance - mat[start-1][node-1]
                dfs(start = node, distance = dist, mat = mat, visited = visited)
    else:
        return None

    return None

def solution(N, road, K):
    answer = 0

    mat = []
    for i in range(N):
        temp = []
        for j in range(N):
            if i == j:
                temp.append(0)
            else:
                temp.append(None)
        mat.append(temp)

    for info in road:
        start = info[0]
        end = info[1]
        dist = info[2]
        if mat[start-1][end-1] != None:
            if mat[start-1][end-1] > dist:
                mat[start-1][end-1] = dist
                mat[end-1][start-1] = dist
        else:
            mat[start-1][end-1] = dist
            mat[end-1][start-1] = dist

    visited = [None] * N
    dfs(start = 1, distance= K, mat = mat, visited = visited)
    for i, visit in enumerate(visited):
        if visit != None:
            answer += 1
    return answer

 

문제의 원 링크는 아래

https://programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달