[SWEA] 2383. 점심 식사시간(Python) / DFS

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl

SW Expert Academy

SW Expert Academy 삼성 SW역량테스트 모의 문제들 중에 개인적으로 난이도 극상의 문제라고 생각한다.

pass까지 3시간 조금 넘게 걸렸다.

• dfs 재귀로 조합 구현하여 계단 선택 완료 - comb() 함수(23분 소요)
• 이후 2시간 될 때까지 열심히 코드 짰는데 50개 tc 중 45개만 맞음.. 하..
• 다음 날 아침 1시간 동안 디버깅해서 겨우 pass 받았다.
• 디버깅으로 고통스러웠지만 내 힘으로 풀어서 뿌듯 ㅎㅎ
• 틀린 이유가 명확했다. 함수 내 처리 순서가 이상했다. 
• downStairs 함수에서 시행착오는 다음과 같다.1. 이번에 계단 내려가는 큐에 들어갈 타이밍인데 이미 꽉 차서 다음 시간에 들어가야 하는 상황에서
  나의 계단 입장 시간과 현 시각이 같은데 큐 길이가 3이면 매 턴마다 +1 해줌
  이 때, 모든 대기 큐의 원소를 해주는 게 아니라, 내 입장시간과 현 시간이 같을 때에만! +1 해줘야 함
  
  2. 계단에서 처리 먼저 해주고 >> 계단 위에서 대기하는 사람 순으로 처리해줘야 하는데
  계단 위 대기 인원 먼저 처리하고 계단에서 빠져나가는 사람을 처리하니까 계속 오차가 발생
  동시에 계단 내려가는 사람 발생 문제가 생겨서 처리 위치를 바꿈
  
  3. 함수 내에서 크게 3가지 작업 처리
  계단 내려가는 사람 처리 => 계단 위에서 대기하는 사람 처리 => 자기 타이밍인데 못 들어간 사람 대기시간 +1 처리 순으로 재정비하니 pass
  
  4. 변수명을 너무 못 지음.. 계단 내려가는 큐를 waitA라고 지어서 자꾸 헷갈림,, 결국 그대로 쓰긴 했다..

 

파이썬 코드는 다음과 같다. 코드가 꽤 길다.

---

from collections import deque

def comb(depth):
    if depth == personCnt:
        A, B = [], []  # 계단별로 사람이 계단에 내려가기까지 걸리는 시간
        for num in range(personCnt):
            if not selection[num]:  # 0번 계단 선택
                sr, sc = stairs[0]
                pr, pc = person[num]
                A.append(abs(pr-sr) + abs(pc-sc) + 1)  # 계단 도착 후 1분 대기 후 내려갈 수 있으므로 + 1
            else:                   # 1번 계단 선택
                sr, sc = stairs[1]
                pr, pc = person[num]
                B.append(abs(pr-sr) + abs(pc-sc) + 1)
        downStairs(A, B)
        return
    for i in range(2):
        if not visited[depth]:
            selection[depth] = i
            visited[depth] = 1
            comb(depth+1)
            visited[depth] = 0
            selection[depth] = 0

def downStairs(A, B):
    global MIN
    # 계단별로 일찍 도착한 순서대로 정렬
    A = deque(sorted(A))
    B = deque(sorted(B))
    waitA, waitB = deque(), deque()
    time = 0
    cnt = 0     # 탈출시킨 사람
    while cnt != personCnt:     # 크게 3가지 작업 처리
        time += 1
        # 계단 내려가는 사람 처리
        awlen, bwlen = len(waitA), len(waitB)
        for _ in range(awlen):
            if waitA and waitA[0] == time:
                waitA.popleft()
                cnt += 1
        for _ in range(bwlen):
            if waitB and waitB[0] == time:
                waitB.popleft()
                cnt += 1

        # 계단 위에서 대기하는 사람 처리
        alen, blen = len(A), len(B)
        for _ in range(alen):
            if A[0] == time and len(waitA) < 3:
                waitA.append(A.popleft() + stair1)
        for _ in range(blen):
            if B[0] == time and len(waitB) < 3:
                waitB.append(B.popleft() + stair2)
                
        # 들어갈 타이밍인데 못 들어간 경우, 해당 원소만 +1 처리
        if len(waitA) == 3:
            for i in range(len(A)):
                if A[i] == time:
                    A[i] += 1
        if len(waitB) == 3:
            for j in range(len(B)):
                if B[j] == time:
                    B[j] += 1
    MIN = min(MIN, time)    # 최솟값 갱신

# main
T = int(input())
for tc in range(T):
    N = int(input())
    stairs = []
    person = []
    personCnt = 0
    A = []
    for i in range(N):
        A.append(list(map(int, input().split())))
        for j in range(N):
            if A[i][j] == 1:
                person.append((i, j))
                personCnt += 1
            elif 2 <= A[i][j] <= 10:
                stairs.append((i, j))
    # 2개의 계단 내려가는 시간
    stair1, stair2 = A[stairs[0][0]][stairs[0][1]], A[stairs[1][0]][stairs[1][1]]
    MIN = float('inf')
    visited = [0] * personCnt
    selection = [0] * personCnt
    comb(0)
    print("#{} {}".format(tc+1, MIN))

 

---

• 고찰 : 오류와의 끝없는 싸움이었다ㅋㅋㅋ 디버깅할 때 정신을 똑바로 차리고 보자니 힘들었지만 금방 엣지 케이스를 떠올릴 수 있었다. 같은 큐여도 여러 번 처리해주는 등 하나하나 동작을 손수 짜줘야해서 힘들었다. + 추가로 변수명을 잘 지어야겠다. 내가 지은 변수명을 내가 헷갈렸다.. 그래도 혼자 잘 풀어냈다. 고생했다! 코딩 절대 포기하지 말자. 노력하면 다 풀리게 되어 있다.