[프로그래머스] 양과 늑대 - Python

🤔 문제

---

 

코딩테스트 연습 - 양과 늑대

 

😀 풀이

---

해당 문제는 DFS를 사용하여 풀이했습니다. 우선 문제 풀이를 위해 아래 두 가지 기능이 필요하다고 생각하여 함수 두 개를 작성했습니다.

• 현재 노드에서 어떤 노드를 가볼 수 있는지 체크하는 함수(getCanGoEdges)
• 가볼 수 있는 노드에 가보며 양과 늑대의 개수를 갱신하는 함수(DFS)

---

# getCanGoEdges 

getCanGoEdges 함수는 이미 방문했던 노드는 생략하고 지금 위치 기준 가볼 수 있는 노드를 구하는 함수입니다.

 

인자로는 i, prev, graph를 받는데 i는 현재 위치, prev는 직전 노드 기준 가볼 수 있었던 노드 입니다. graph는 노드 간의 연결 상태를 나타냅니다.

 

직전 노드 기준 가볼 수 있었던 노드는 i 위치에 오더라도 가볼 수 있는 노드입니다. i 위치만 빼고 말이죠! 해당 로직은 코드를 확인해주세요.

---

# DFS

DFS의 종료 조건은 다음과 같습니다.

• 양과 늑대의 개수가 같은 경우 정답을 갱신하며 함수를 종료시킵니다.
• 갈 수 있는 노드가 없는 경우 정답을 갱신하며 함수를 종료시킵니다.

종료 조건이 아닌 경우 canGoEdges를 살펴보며 DFS를 진행시킵니다.

---

💻 풀이 코드는 아래와 같습니다.

# 현재 위치에서 갈 수 있는 노드 찾기
def getCanGoEdges(i, prev, graph):
    canGoEdges = [edge for edge in prev if edge != i]
    for j in range(len(graph)):
        if graph[i][j] == True:
            canGoEdges.append(j)
    return canGoEdges

# 현재 위치(i) 기준으로 갈 수 있는 곳 가보기 -> DFS
def DFS(i, s, w, prev, graph, info):
    global answer
    canGoEdges = getCanGoEdges(i, prev, graph)
    if s == w or not canGoEdges:
        if answer < s:
            answer = s
        return
    for edge in canGoEdges:
        if info[edge] == 0: # 가려는 노드에 양이 있는 경우
            DFS(edge, s + 1, w, canGoEdges, graph, info)
        else: # 가려는 노드에 늑대가 있는 경우
            DFS(edge, s, w + 1, canGoEdges, graph, info)

def solution(info, edges):
    global answer
    answer = 1
    graph = [[False] * len(info) for _ in range(len(info))]
    for x, y in edges:
        graph[x][y] = True
    DFS(0, 1, 0, [0], graph, info)
    return answer