Punch!

1. 문제 설명

주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 한다.

어떤 차량이 입차된 후에 출차된 내역이 없다면, 23:59에 출차된 것으로 간주한다.

00:00부터 23:59까지의 입/출차 내역을 바탕으로 차량별 누적 주차 시간을 계산하여 요금을 일괄로 정산한다.

- 누적 주차 시간이 기본 시간 이하라면, 기본 요금을 청구한다.

- 누적 주차 시간이 기본 시간을 초과하면, 기본 요금에 더해서, 초과한 시간에 대해서 단위 시간 마다 단위 요금을 청구한다.

(단, 초과한 시간이 단위 시간으로 나누어 떨어지지 않으면, 올림한다.)

차량 번호가 작은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아서 반환하라.

2. 코드

import math

def solution(fees, records):
    default_time, default_fee, unit_time, unit_fee = fees[0], fees[1], fees[2], fees[3]
    
    record_dict = {}
    answer = {}
    
    # 출입 기록 저장
    for record in records:
        a, b, _ = record.split(' ')
        
        if b in record_dict.keys():
            record_dict[b].append(a)
        else:
            record_dict[b] = [a]    

    
    # 정산
    for car, in_out in record_dict.items():
        park_m = 0

        while in_out:
            if len(in_out) == 1:
                in_h, in_m = map(int, in_out[0].split(':'))
                out_h, out_m = 23, 59
                
                if out_m >= in_m:
                    park_m += (out_h - in_h) * 60 + (out_m - in_m)
                else:
                    park_m += (out_h - 1 - in_h) * 60 + (out_m + 60 - in_m)
                break
            
            else:
                in_h, in_m = map(int, in_out[0].split(':'))
                out_h, out_m = map(int, in_out[1].split(':'))
                
                if out_m >= in_m:
                    park_m += (out_h - in_h) * 60 + (out_m - in_m)
                else:
                    park_m += (out_h - 1 - in_h) * 60 + (out_m + 60 - in_m)
                    
                in_out = in_out[2:]
        
        
        if park_m <= default_time:
            answer[car] = default_fee
        else:
            answer[car] = default_fee + math.ceil((park_m - default_time) / unit_time) * unit_fee
        

    return [v for k,v in sorted(answer.items())]

3. 설명

우선 출입 차량에 대해서 딕셔너리로 기록하는데, 이때 in과 out은 순서가 정해져있기 때문에 신경쓰지 않았다.

만약 이미 딕셔너리에 저장되어있는 차량이라면, 딕셔너리 value인 리스트에 값을 추가하고,

그렇지 않은 경우에는 리스트를 추가한다.

저장한 출입 기록을 for문으로 돌면서 정산을 한다.

만약 in_out이 1인 경우에는 in 만 하고 out을 안 한 경우이기 때문에 나간 시간을 23:59으로 설정해준다.

math 라이브러리의 ceil 함수를 사용해서 올림 처리해준다.

1. 문제 설명

선행 스킬 : 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬

예) 스파크 → 라이트닝 볼트 → 썬서

- 썬더를 배우려면 라이트닝 볼트를 먼저 배워야 함

- 라이트닝 볼트를 배우려면 스파크를 먼저 배워야 함

선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 반환하라.

2. 코드

def solution(skill, skill_trees):
    answer = 0
    
    for skill_tree in skill_trees:
        s = ''
        
        for i in skill_tree:
            if i in skill:
                s += i

        if skill[:len(s)] == s:
            answer += 1
    
    return answer

3. 설명

skill_tree의 문자 하나씩을 조사해가면서 그 문자가 skill에 존재할 경우 s에 잠시 저장한다.

skill의 처음부터 s의 길이만큼의 문자열이 s와 같다면, 선행 스킬이 잘 반영된 문자열이다.

1. 문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶다.

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해, 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만든다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 반환하라.

- 제한 사항

1. scoville의 길이는 2 이상 1,000,000 이하

2. K는 0 이상 1,000,000,000 이하

3. scoville의 원소는 각각 0 이상 1,000,000 이하

4. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return

2. 코드

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    if scoville[0] >= K:
        return answer
    
    while len(scoville) > 1:
        answer += 1

        min1 = heapq.heappop(scoville)
        min2 = heapq.heappop(scoville)
        
        heapq.heappush(scoville, min1 + (min2 * 2))
        
        if scoville[0] >= K:
            return answer
        else:
            continue
        
    return -1

3. 설명

heap을 쓴다는 것을 안다면 쉽게 풀 수 있는 문제였다.

최솟값을 반환해야 하기 때문에 힙을 사용한다.

중간에 한 개의 테스트 케이스에서 오답이 나오는 경우가 있었는데,

이는 처음부터 모든 스코빌 지수가 K보다 큰 경우 (섞을 필요가 없는 경우) 0을 반환해야 하는 케이스였다.

import heapq

heapq.heapify(list)

heapq.heappop(list)

heapq.heappush(list, value)

이 문법만 알면 python에서의 heap은 문제 없을 것 같다.

참고로, heapq는 최소힙이 기본이다. 따라서 최대힙은 다음과 같이 선언한다.

# heappush
for value in values:
	heapq.heappush(heap, -value)
 
# heappop
for i in range(5):
	print(-heapq.heappop(heap))

1. 문제 설명

땅따먹기 게임을 하려고 한다.

땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있다.

1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 한다.

단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있다.

예)

|1|2|3|5|

|5|6|7|8|

|4|3|2|1|

1행에서 네번째 칸 (5)를 밟았다면, 2행의 네번째 칸 (8)은 밟을 수 없다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최댓값을 반환하라.

2. 코드

(1) 1차 시도 - 런타임 에러

answer = 0

def dfs(land, row, col, tot):
    global answer
    tot += land[row][col]

    if row == len(land) - 1:
        if answer < tot:
            answer = tot
        return 
    

    for i in range(4):
        if i == col:
            continue
        dfs(land, row+1, i, tot)
    
    
def solution(land):
    global answer
    
    for col in range(4):
        dfs(land, 0, col, 0)
    
    return answer

(2) 2차 시도 - DP

def solution(land):
    for i in range(1, len(land)): # 행 반복
        for j in range(4): # 열 반복
            land[i][j] += max(land[i-1][:j] + land[i-1][j+1:])
    
    return max(land[-1])

3. 설명

우선 처음에 짠 코드는 깊이 우선 탐색 (DFS) 방법을 사용해서 구현했다.

재귀 함수로 열을 반복하며 (단, 연속된 동일한 열은 제외) sum을 누적하는 방식으로 했는데,

재귀로 호출되면서 알 수 없는 런타임 에러가 떴다.. (반례도 다 조사했을 때 문제 없었다ㅠㅠ)

그래서 다이나믹 프로그래밍으로 다시 구현했다.

이전 행에서의 최댓값을 뽑아서 현재 행에 더하는 방식으로 하여,

맨 마지막 행에서의 최댓값을 택하면 답이 된다!

1. 문제 설명

게임 캐릭터를 4가지 명령어를 통해 움직이려 한다. 

- U : 위쪽으로 한 칸 가기

- D : 아래쪽으로 한 칸 가기

- R : 오른쪽으로 한 칸 가기

- L : 왼쪽으로 한 칸 가기

캐릭터는 좌표평면의 (0, 0) 위치에서 시작하고, 좌표평면의 경계는 (-5, -5), (-5, 5), (5, 5), (5, -5)이다.

예) "ULURRDLLU"

게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 한다.

위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본 길의 길이는 7이 된다.

(8, 9번 명령어에서 움직인 길은 2, 3번 명령어에서 이미 거쳐 간 길)

명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 반환하라.

2. 코드

(1) 내 코드

def solution(dirs):
    dx = [0, 0, 1, -1] # UDRL
    dy = [1, -1, 0, 0] # UDRL
    x, y = 0, 0
    
    garo = [ [False for _ in range(10)] for _ in range(11) ]
    saero = [ [False for _ in range(10)] for _ in range(11) ]
    
    answer = 0
    for dir in dirs:
        if dir == 'U':
            new_x = x + dx[0]
            new_y = y + dy[0]
        elif dir == 'D':
            new_x = x + dx[1]
            new_y = y + dy[1]
        elif dir == 'R':
            new_x = x + dx[2]
            new_y = y + dy[2]
        elif dir == 'L':
            new_x = x + dx[3]
            new_y = y + dy[3]
        
        if new_x < -5 or new_x > 5 or new_y < -5 or new_y > 5:
            continue
        
        if dir == 'R':
            if garo[5 - new_y][5 + x] == False:
                garo[5 - new_y][5 + x] = True
                answer += 1
        elif dir == 'L':
            if garo[5 - new_y][5 + new_x] == False:
                garo[5 - new_y][5 + new_x] = True
                answer += 1
        elif dir == 'U':
            if saero[5 + new_x][5 - new_y] == False:
                saero[5 + new_x][5 - new_y] = True
                answer += 1
        elif dir == 'D':
            if saero[5 + new_x][5 - y] == False:
                saero[5 + new_x][5 - y] = True
                answer += 1
        
        x, y = new_x, new_y
        
        
    return answer

(2) set 활용한 코드

def solution(dirs):
    s = set()
    d = {'U': (0,1), 'D': (0, -1), 'R': (1, 0), 'L': (-1, 0)}
    x, y = 0, 0
    
    for i in dirs:
        nx, ny = x + d[i][0], y + d[i][1]
        if -5 <= nx <= 5 and -5 <= ny <= 5:
            s.add((x,y,nx,ny))
            s.add((nx,ny,x,y))
            x, y = nx, ny
            
    return len(s)//2

3. 설명

(1) 내 코드

우선 내가 짠 코드는.. 정말 있는 그대로의 날 것의 코드이다.. ㅎ 좀 창피하긴 한데, set을 활용할 생각을 못했어서 이렇게 풀 수밖에 없었다ㅜㅠ

흔히 다이나믹 프로그래밍에서 하는 것처럼 방문 여부를 저장하기 위해 배열을 만들어준다.

단, UP, DOWN은 'garo[11][10]' 배열을,

LEFT, RIGHT는 'saero[11][10]' 배열이다.

배열의 인덱스와 좌표를 맞춰주기 위해서 규칙을 찾아봤을 때,

각각 5-x 또는 5+x, 5-y, 5+y를 해주면 맞춰진다.

각각의 경우를 조건문으로 해서 하나씩 조사해 나가면 된다.

(2) set 활용한 코드

우선 UDRL을 딕셔너리로 선언하고, 좌표 범위를 넘어서는지 조사한다.

그리고는 (시작좌표 x, 시작좌표 y, 도착좌표 x, 도착좌표 y)와 (도착좌표 x, 도착좌표 y, 시작좌표 x, 시작좌표 y)를 모두 집합에 넣는다.

- 집합에 넣는 이유 : 중복되는 이동 쌍이 없도록

- 마지막에 2로 나눠주는 이유 : 시작과 도착 좌표를 모두 넣어줬기 때문에, 그 절반 값이 이동 횟수임

배울 점이 많았던 코드였다. 이동 경로를 string으로 저장하지 않고, 시작과 끝 좌표 쌍을 모두 저장하는 방식,

그리고 집합을 사용하여 중복 제거하는 것까지!

1. 문제 설명

정수로 이루어진 배열 numbers가 있다.

배열에서 자신보다 뒤에 있는 숫자 중에서, 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 한다.

정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 반환하라.

단, 뒷 큰수가 존재하지 않는 원소는 -1을 담는다.

예시)

- numbers = [2, 3, 3, 5]

정답 : [3, 5, 5, -1]

- numbers = [9, 1, 5, 3, 6, 2]

정답 : [-1, 5, 6, 6, -1, -1]

2. 코드

(1) 1차 시도

def solution(numbers):
    answer = []
    
    for i in range(len(numbers)):
        for j in range(i+1, len(numbers)):
            if numbers[i] < numbers[j]:
                answer.append(numbers[j])
                break
        if len(answer) != (i+1):
            answer.append(-1)
    
    return answer

(2) 2차 시도

def solution(numbers):
    answer = [-1 for _ in range(len(numbers))]
    stack = []
    
    for i in range(len(numbers)):
    
        while stack and numbers[stack[-1]] < numbers[i]:
            answer[stack.pop()] = numbers[i]
        
        stack.append(i)
        
    return answer

3. 설명

이 문제가 되게 단순해 보였지만, 시간 초과를 극복하려면 새로운 관점이 필요하기 때문에 어려웠다.

많은 사람들의 코드를 봤을 때, 2차 시도 코드와 비슷하거나 동일하다.

그래서 나는 어떻게 stack을 도입할 시도를 하게 되었는지를 생각해보기로 했다.

처음에는 절대로 저런 생각이 나지 않기 때문이다..

index 하나 하나씩을 해결해나가는 식이 아니라, 바로 뒤에 큰 수가 없다면 잠시 스택에 넣고 대기하는 형식이다.

이렇게 하나씩 뿌시는 경우에는 현재 인덱스에서 그 뒤의 인덱스 이후를 다 비교해봐야 하기 때문에, $O(n^2)$이 된다.

검토하고 있는 인덱스의 그 다음 인덱스 시점에서 바라본다.

만약 그 인덱스가 큰 수를 찾지 못했다면 스택에 넣는다!

기본적으로 현재 인덱스를 스택에 넣어주고, 조건 맞을 시에 pop() 하도록 구현한다.

위의 그림이 단계를 거치면서 스택의 변화를 보여준다.

즉, for 문이 돌아가는 그 시점의 인덱스는 answer 값이 변하는 시점의 인덱스가 아니라, 비교대상이라고 생각하면 된다!

1. 문제 설명

철수와 동생은 롤케이크를 나눠 먹으려고 한다.

두 사람은 롤케이크 길이, 토핑의 개수보다 토핑 종류를 더 중요하게 생각한다.

topping 배열이 주어졌을 때, "동일한 가짓수의 토핑"을 나눠 먹을 수 있도록 하는 방법의 가짓수를 반환하라.

예를 들어, [1, 2, 1, 3, 1, 4, 1, 2] 토핑은 [1, 2, 1, 3], [1, 4, 1, 2] 또는 [1, 2, 1, 3, 1], [4, 1, 2]로 나눌 수 있으므로, 총 2가지이다.

[1, 2, 3, 1, 4]는 어떻게 나누든 공평한 토핑의 종류를 가질 수 없으므로, 0이다.

2. 코드

(1) 1차 시도

def solution(topping):
    answer = 0
    
    for i in range(1, len(topping)):
        a = topping[:i]
        b = topping[i:]
        
        if len(set(a)) == len(set(b)):
            answer += 1
    
    return answer

(2) 2차 시도

from collections import Counter

def solution(topping):
    topping_dict = Counter(topping)
    topping_set = set()
    answer = 0
    
    for i in topping:
        topping_dict[i] -= 1
        topping_set.add(i)
        
        if topping_dict[i] == 0:
            topping_dict.pop(i)
        
        if len(topping_set) == len(topping_dict):
            answer += 1
    
    return answer

3. 설명

배열 슬라이싱이 $O(N)$이 걸려서, 결국 $O(N^2)$ 수행시간이 걸리게 된다. 그래서 시간 초과가 났던 것이다ㅜ

슬라이싱을 안 하고, 한번의 검토로 기준선 앞, 뒤를 모두 검토할 수 있는 방식으로 다시 코드를 짰다.

Counter dictionary를 사용해서 토핑 종류에 대한 개수를 저장하고, 기준 앞쪽에 대해서 원소를 하나씩 지워나간다.

그러면서 집합에 넣어서 unique한 원소들의 개수를 구한다.

topping_set과 topping_dict 길이가 같다면 answer + 1 해준다.

1. 문제 설명

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있다.

사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"이다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 반환하라.

예)

"AAAAE" → 6

"AAAE" → 10

"I" → 1563

"EIO" → 1189

2. 코드

from itertools import product

def solution(word):
    dictionary = ["".join(list(j)) for i in range(1, 6) for j in product(['A', 'E', 'I', 'O', 'U'], repeat=i)]
    dictionary = sorted(dictionary)
    
    return dictionary.index(word) + 1

3. 설명

사전 순으로 배열은 sorted 함수로 자동 배열할 수 있어서, 이 문제의 핵심은 사전에 들어갈 요소들을 구성하는 데에 있다.

from itertools import product를 불러와서 길이 5 이하로 구성할 수 있는 조합 모두를 구한다.

예를 들어서 다음과 같은 경우에는 repeat=2 이므로 길이가 2인 모든 조합의 수를 구한다.

A = [1,2,3]
list(itertools.product(A, repeat=2))

[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

따라서, 문제에서는 가변길이이므로 repeat=i를 두고, i를 for 문으로 1부터 5까지 반복하도록 한다.

[ j for i in range(1, 6) for j in product(['A', 'E', 'I', 'O', 'U'], repeat=i) ]

이렇게 했을 때 결과는 다음과 같다.

- 길이 1 : ('A',), ('E',), ('I',), ('O',), ('U',)

- 길이 2 : ('A', 'A'), ('A', 'E'), ('A', 'I'), ('A', 'O'), ('A', 'U'), ('E', 'A'), ('E', 'E'), ('E', 'I'), ('E', 'O'), ('E', 'U'), ('I', 'A'), ('I', 'E'), ('I', 'I'), ('I', 'O'), ('I', 'U'), ('O', 'A'), ('O', 'E'), ('O', 'I'), ('O', 'O'), ('O', 'U'), ('U', 'A'), ('U', 'E'), ('U', 'I'), ('U', 'O'), ('U', 'U')

- 길이 3 : ('A', 'A', 'A'), ('A', 'A', 'E'), ('A', 'A', 'I'), ('A', 'A', 'O'), ('A', 'A', 'U'), ('A', 'E', 'A'), ('A', 'E', 'E'), ('A', 'E', 'I'), ('A', 'E', 'O'), ('A', 'E', 'U'), ('A', 'I', 'A'), ('A', 'I', 'E'), ... ,('U', 'O', 'O'), ('U', 'O', 'U'), ('U', 'U', 'A'), ('U', 'U', 'E'), ('U', 'U', 'I'), ('U', 'U', 'O'), ('U', 'U', 'U')

...

- 길이 5 : ('A', 'A', 'A', 'A', 'A'), ('A', 'A', 'A', 'A', 'E'), ('A', 'A', 'A', 'A', 'I'), ('A', 'A', 'A', 'A', 'O'), ('A', 'A', 'A', 'A', 'U'), ('A', 'A', 'A', 'E', 'A'), ('A', 'A', 'A', 'E', 'E'), ('A', 'A', 'A', 'E', 'I'), ('A', 'A', 'A', 'E', 'O'), ('A', 'A', 'A', 'E', 'U'), ... ('U', 'U', 'U', 'U', 'U', 'U')

이 j들을 join 해주고, dictionary 배열 sorting만 해주면 된다.

1. 문제 설명

어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. 메시지를 압축하더라도 전달되는 정보가 바뀌지 않도록 하기 위해서, LZE(Lempel-Ziv-Welch) 압축을 구현하기로 했다.

LZW 압축은 다음 과정을 거친다.

- 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.

- 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.

- w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.

- 입력에서 처리되지 않은 다음 글자가 남아있다면 (c), w+c에 해당하는 단어를 사전에 등록한다.

- 두번째 단계로 돌아간다.

압축 알고리즘은 영문 대문자만 처리한다고 할 때, 사전은 다음과 같이 초기화된다.

예를 들어 입력으로 'KAKAO'가 들어온다고 하자.

이 과정을 거쳐 다섯 글자의 문자 KAKAO가 4개의 색인 번호 [11, 1, 27, 15]로 압축된다.

문자열 msg에 대해 압축한 결과를 배열로 출력하라.

2. 코드

import string

def find_max_str(msg, index):
    max_str = ''

    for i in msg:
        if max_str + i in index.keys():
            max_str += i
        else:
            return max_str

    return max_str
    
        
def solution(msg):
    keys = [ i for i in string.ascii_uppercase ]
    values = [ i for i in range(1, 27) ]
    index = { k:v for k, v in zip(keys, values) }
    
    answer = []

    while True:
        max_str = find_max_str(msg, index)
        answer.append(index[max_str])

        msg = msg[len(max_str):]

        if len(msg) == 0:
            break
        index[max_str + msg[0]] = len(index.keys()) + 1
        
    
    return answer

3. 설명

- 우선 사전 초기화를 해주는데, dictionary를 만들 때 문제에서 제시한거랑 다르게 key를 알파벳으로, value는 1부터 26까지로 초기화했다. 이유는 해당 문자(또는 문자열)이 dictionary에 존재하는지 확인하기가 편하기 때문이다.

- find_max_str()으로 사전에 존재하는 최대 문자열을 확인하여, max_str를 반환한다.

msg에 있는 알파벳 하나씩을 더해가면서 dictionary에 있는지 확인하여, 존재하지 않을 때까지의 문자열을 반환한다.

- max_str의 길이를 통해 이후에 조사할 msg를 만들어준다. (msg = msg[len(max_str):])

- 마지막에 max_str + msg[0] 문자열을 dictionary에 추가해준다.

1. 문제 설명

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임이다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리하다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길이다. 캐릭터는 동, 서, 남, 북으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없다.

첫번째 방법은 11칸을 지나서 도착이며, 두번째 방법은 15칸을 지나서 도착이다.

만약, 상대 팀이 자신의 티 진영 주변에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있다.

이때, 상대 팀 진영에 도착하기 위해 지나가야 하는 칸의 개수의 최솟값을 반환하여라.

2. 코드

(1) 1차 시도

dr = [1, 0, -1, 0] # row : 하 우 상 좌
dc = [0, 1, 0, -1] # column : 하 우 상 좌
minimum = 10001

def dfs(maps, now_r, now_c):
    global minimum
    n, m = len(maps), len(maps[0])

    if (now_r == n-1) and (now_c == m-1): # 적 진영에 도착한 경우
        if maps[now_r][now_c] < minimum:
            minimum = maps[now_r][now_c]
            return minimum

    for i in range(4):
        new_r = now_r + dr[i]
        new_c = now_c + dc[i]
        
        if new_r >= 0 and new_r <= (n-1) and new_c >= 0 and new_c <= (m-1):
            if maps[new_r][new_c] == 1:

                maps[new_r][new_c] = maps[now_r][now_c] + 1
                dfs(maps, new_r, new_c)
                maps[new_r][new_c] = 1
        
def solution(maps):
    global minimum
    now_r, now_c = 0, 0
    
    dfs(maps, now_r, now_c)
    
    if minimum == 10001:
        return -1
    
    return minimum

효율성 테스트를 통과하지 못했다.

(2) 2차 시도

from collections import deque

dr = [1, 0, -1, 0] # row : 하 우 상 좌
dc = [0, 1, 0, -1] # column : 하 우 상 좌

def bfs(maps, now_r, now_c):
    n, m = len(maps), len(maps[0])
    
    queue = deque()
    queue.append([now_r, now_c])
    
    while queue:
        r, c = queue.popleft()
        
        for i in range(4):
            new_r = r + dr[i]
            new_c = c + dc[i]

            if new_r >= 0 and new_r <= (n-1) and new_c >= 0 and new_c <= (m-1):
                if maps[new_r][new_c] == 0: 
                    continue

                if maps[new_r][new_c] == 1:
                    maps[new_r][new_c] = maps[r][c] + 1
                    queue.append([new_r, new_c])
                    
    return maps[n-1][m-1]
        
def solution(maps):
    r, c = 0, 0
    ans = bfs(maps, r, c)
    
    if ans == 1:
        return -1
    
    return ans

3. 설명

BFS로 문제를 풀면, 어떻게 하더라도 계속 시간 초과가 발생한다ㅠㅠ

그래서 아예 DFS로 바꿔서 풀었다.

- deque를 사용하여 현재 위치를 큐에 넣어두고, popleft()를 하여 현재 위치를 받아온다.

- 현재 위치 기준 상, 하, 좌, 우를 이동하면서 맵을 벗어나지 않고 1 값을 가지는 위치 모두를 큐에 저장한다. → 너비 우선 방식!

- 큐에 저장된 [행, 열] 좌표에 대해 maps 배열의 원소를 이전 좌표에 +1 한 값으로 바꿔주어, 해당 좌표까지 오는데 얼만큼의 비용이 들어가는지 저장한다.

- 만약 dfs()에서 반환한 값이 1인 경우는 적의 진영에 도달하지 못했다는 의미이므로 -1을 반환한다.

1. 최솟값을 갱신해줄 필요가 없다.

- DFS는 최단경로를 보장한다.

2. visited로 방문 여부를 판단할 필요가 없다.

- maps의 값이 1일 때만 방문하도록 하여 따로 방문 여부를 저장하는 배열이 필요하지 않다,