[소프티어] Lv.3 함께하는 효도 (파이썬)

DFS, 백트래킹 문제

https://softeer.ai/practice/7727

Softeer - 현대자동차그룹 SW인재확보플랫폼

---

문제 설명

각각의 친구들이 현재 자신의 위치에서 이동할 수 있는 길이 4의 경로들 중에서, 모든 친구들과 경로가 겹치지 않으면서 과일을 최대로 수확할 수 있는 수확량을 구하는 것

---

✏️ 짚고 넘어갈 Point

1) DFS에서 특정 level에 도달할 때까지 기록해두었던 임시 배열을 result 배열에 추가하고 싶을 때

 

잘못된 코드

if level == 4:
    # 얕은 복사로 인해 값이 덮어씌워지는 문제 발생 (result가 변경됨에 따라 그 이전에 추가했던 값들도 변경됨)
    cand[idx].append(result)
    return

위의 조건문 안에서 result를 출력해보았을 때에는 올바른 결과가 나왔다.

하지만, result를 cand 배열에 삽입한 후 cand를 출력해보았을 때에는 값이 덮어씌워져서 중복된 결과가 나왔다.

 

즉, cand[0] 값이 cand[1]의 값으로 덮어씌워지는 문제가 있었다. 

이 이유는 바로 리스트의 얕은 복사 문제 때문이었다.

result 리스트는 재귀 호출마다 변경됨에 따라 모든 cand 리스트가 동일한 result 객체를 참조하게 된 것이다.

 

올바른 코드

if level == 4:
    cand[idx].append(result[:])
    # cand[idx].append(copy.deepcopy(result))
    return

이러한 문제를 해결하기 위해선 result를 새로운 객체로 복사하여 cand[idx]에 추가해야한다.

 

그 방법으로는 크게 2가지가 있는데, 아래와 같다.

1) copy 모듈의 deepcopy 시용

2) 리스트의 슬라이싱 [:] 사용

---

2) extend()

상황

i = [(0,0),(1,0),(2,0),(3,0)]인데 각각의 원소들을 arr 배열에 넣고싶다.

이때, for문을 사용해서 원소 하나씩 append 하는게 아닌 코드 한줄로 끝내고 싶다고 가정하자.

 

 

해결법

i = [(0, 0), (1, 0), (2, 0), (3, 0)]
arr = []
arr.extend(i)

'''
출력 결과:
[(0, 0), (1, 0), (2, 0), (3, 0)]
'''​

---

3) 여러 요소들을 pop()하고 싶을 때

상황

arr = [(0,0),(1,0),(2,0),(3,0),(4,0),(5,0)]이라고 가정하자.

이때, 한번에 4개의 원소를 pop()하고 싶다.

 

 

해결법

 

pop()이 아닌 인덱스 슬라이싱을 사용하면 된다.

 

arr = arr[:-4]

---

💡 풀이코드 (12번 실패 - DFS, Cartesian Product)

import sys
import copy
n, m = map(int, sys.stdin.readline().split())
graph = []
start = []
visited = [[0] * n for _ in range(n)]

dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
cand = [[] for _ in range(m)]
result = [[] for _ in range(4)]

for _ in range(n):
    l = list(map(int, sys.stdin.readline().split()))
    graph.append(l)

for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    start.append((x-1, y-1))
    visited[x-1][y-1] = 1 


def dfs(level, idx, xx, yy):
    if level == 4:
        # cand[idx].append(result) # 얕은 복사로 인해 값이 덮어씌워지는 문제 발생 (result가 변경됨에 따라 그 이전에 추가했던 값들도 변경됨)
        cand[idx].append(result[:])
        return

    for i in range(4):
        nx = xx + dy[i]
        ny = yy + dx[i]

        if 0 <= nx < n and 0 <= ny < n:
            if visited[nx][ny] == 0:
                visited[nx][ny] = 1
                result[level] = (nx, ny, graph[nx][ny])
                dfs(level + 1, idx, nx, ny)
                visited[nx][ny] = 0
for j in range(len(start)):
    visited[start[j][0]][start[j][1]] = 1 
    result[0] = (start[j][0], start[j][1], graph[start[j][0]][start[j][1]])
    dfs(1, j, start[j][0], start[j][1])

answer = 0
coord = []
def back(level, curr):
    global answer, coord
    if level == m:
        answer = max(answer, curr)
        return

    for i in cand[level]:
        duplicated = False
        for j in range(4):
            if i[j] in coord:
                duplicated = True
        if duplicated == True : continue
        coord.extend(i)
        n_curr = sum(xx[2] for xx in i)
        back(level + 1, curr + n_curr)
        # coord.pop(*i)
        coord = coord[:-4]

back(0, 0)
print(answer)

 

1~12번의 테스트케이스 중 12번만 실패하였다.

블로그에 나와있는 다른 여러 사람들의 코드를 돌려봤을 시에도 12번만 실패하는 경우가 많았다.

 

밑의 다른 사람의 풀이에 비해선 위의 코드가 비효율적인 것 같다.

 

그 이유는

1) DFS로 한 사람마다 갈 수 있는 길이가 4짜리의 경로를 모두 찾은 후, 

2) 백트래킹으로 각각의 사람들의 경로를 조합하는 작업을 

나누어서 진행하기 때문이다.

 

접근 방식

1) DFS

각각의 친구들이 현재 자신의 위치에서 이동할 수 있는 길이 4의 모든 경로를 DFS를 통해 찾는다. (친구들간 중복 고려 X)

• result 배열에는 depth가 1~4일 때의 x,y 좌표와 graph 값을 차례대로 기록한다.
• 이렇게 만들어진 해당 친구가 갈 수 있는 길이가 4인 경로(result 배열)을 cand[해당 친구의 번호]에 하나씩 추가해준다.

2) 백트래킹 (Carterisan Product)

위의 DFS에서 만든 각각의 친구들이 현재 위치에서 갈 수 있는 모든 경로를 담은 cand 배열을 활용한다.

• 백트래킹을 돌며 만약 현재 level이 친구의 명수와 동일하다면 answer(과일의 총합)을 비교하여 max값을 기록한다.
• 아래는 product를 백트래킹으로 구현한 코드이다. 즉, 각각의 친구가 갈 수 있는 경로를 하나씩 조합하는 과정에서 경로가 서로 겹치는지 조건을 확인하고, 만약 경로가 겹치지 않는다면 level을 올려 재귀 탐색을 계속한다.

for i in cand[level]:
        duplicated = False
        for j in range(4):
            if i[j] in coord:
                duplicated = True
        if duplicated == True : continue
        coord.extend(i)
        n_curr = sum(xx[2] for xx in i)
        back(level + 1, curr + n_curr)
        # coord.pop(*i)
        coord = coord[:-4]

• 재귀탐색에서 리턴한 후에는 해당 경로를 pop()해준다.

---

💡 다른 사람 풀이코드 ( 성공 - DFS)

import sys
import copy
n, m = map(int, sys.stdin.readline().split())
graph = []
start = []
visited = [False] * m # 각각의 친구들이 과일을 수확했는지를 나타내는 여부

dx, dy = [-1,1,0,0], [0,0,-1,1]

result = [[] for _ in range(4)]
answer = 0

for _ in range(n):
    l = list(map(int, sys.stdin.readline().split()))
    graph.append(l)

for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    start.append((x-1, y-1))


def dfs(level, idx, x, y, curr):
    global answer
    
    value = graph[x][y]
    visited[idx] = True
    graph[x][y] = 0 # 다시 선택 안되도록 0으로 변경 (다른 친구와 경로가 겹치지 않도록)
    
    if level == 4:
        if all(visited):
            answer = max(answer, curr + value)
        
        for s in range(idx, len(start)):
            if not visited[s]:
                dfs(1, s, start[s][0], start[s][1], curr + value)

        visited[idx] = False
        graph[x][y] = value
        return
        
            
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if 0 <= ny < n and 0 <= nx < n:
            dfs(level + 1, idx, nx, ny, curr + value)

    visited[idx] = False
    graph[x][y] = value

dfs(1, 0, start[0][0], start[0][1], 0)
print(answer)

---

* 참고 문헌

https://woohyun-king.tistory.com/392

[소프티어 7727번] 함께하는 효도

https://tigerfrom2.tistory.com/407

소프티어 - 함께하는 효도(C++)

https://appdung-ioss.tistory.com/222

Softeer Level3: [HSAT 2회 정기 코딩 인증평가 기출] 사물인식 최소 면적 산출 프로그램 (Back Tracking / wi