1. 그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘은 다음과 같이 불리기도 한다.

• 욕심쟁이 방법
• 탐욕적 방법
• 탐욕 알고리즘 

이렇게 불리는 이유는 단어의 정의 때문이다.

Greedy
1. 욕심 많은
2. 탐욕적인

최적화 문제를 해결하는 알고리즘 중 하나이다. 각 단계에서 선택가능한 해들 중에서 가장 좋은 해를 찾는 문제이다. 데이터 간의 관계를 고려하지 않고 수행 과정에서 단계에 최적해인 최솟값 또는 최댓값을 가진 데이터를 선택한다.이를 '근시안적 선택'이라고 말하기도 한다.  

각각의 단계에서의 선택(부분해)을 모아서 문제의 최적해를 도출한다.

2. 그리디 알고리즘의 특징

섬 A에서 섬 C를 가는 최소 경로를 구하는 문제를 통해 알아보겠다.

섬 A 에서 섬 C로 가려면 A to B, B to C로 가야한다.

A to B 의 부분해, B to C 의 부분해를 구해서 문제의 최적해를 구한다.

여기서 특징을 알 수 있다. 각 단계에서 구한 답은 절대로 번복하지 않으며, 이후 단계는 이전 단계의 데이터를 통해 계산하지 않는다.(독립적)

다시 특징을 정리하자면

1. 한번 선택한 해답 (각각의 단계에서 구한 부분해)은 절대로 번복하지 않는다. 즉, 선택한 데이터를 버리고 다른 것을 취하지 않는다.

2. 알고리즘은 단순하며, 매우 제한적인 문제들만 그리디 알고리즘으로 해결가능하다.

3. 다른 알고리즘에 비해 계산시간이 매우 빠른 편이다.

그리디 알고리즘을 문제를 해겷하기 위해선 각각의 최적해들이 항상 최적임을 보장해야한다. 

3. 그리디 알고리즘과 동적 계획법의 차이

( Greedy Algorithm vs Dynamic Programming(DP))

4. 그리디 알고리즘 예시 

다음은 그리디 알고리즘을 사용하는 예시이다.

4.1 동전 거스름돈 ( Coin Change)

https://giliit.tistory.com/61

4.2 최소신장 트리 ( MST, Minimum Spanning Tree)

• Kruskal MST
• Prim MST

4.3 최단경로 찾기 ( Shortest Path)

• Dijkstra Shortest Path

4.4 부분 배낭 문제 ( Fractional Knapsack)

4.5 부분 집합 문제 ( Set Covering)

4.6 작업 스케줄링 ( Task Scheduling)

4.7 허프만 압축 ( Huffman Coding)

1. 알고리즘(Algorithm)이란?

문제를 해결하는 단계적 절차 또는 방법이다. 

입력 -> 알고리즘 -> 결과  -> 문제 해결

특성

• 정확성 : 알고리즘은 주어진 입력에 대해 올바른 해를 주어야 한다. 즉, 모든 입력에 대해 올바른 답을 출력해야 한다. 
• 수행성 : 알고리즘의 각 단계는 컴퓨터에서 수행이 가능하여야 한다. 애매모호한 표현을 사용하면 안된다.
• 유한성 : 알고리즘은 유한 시간 내에 종료되어야 한다. 매우 오래 걸리면 알고리즘의 가치를 잃는다.
• 효율성 : 알고리즘은 효율적일수록 그 가치가 높아진다. 항상 시간적, 공간적인 효율성을 갖도록 고안되어야 한다.

2. 알고리즘의 표현 방법

2-1. 말로 표현된 알고리즘

첫 카드의 숫자를 읽고 기억한다.
다음 카드의 숫자를 읽고, 기억한 숫자와 비교한다.
비교 후 큰 숫자를 기억한다.
다음에 읽을 카드가 있으면 line 2로 간다.
기억한 숫자가 최대 숫자다.

2-2. 의사 코드(pseudo code)로 표현된 알고리즘

max = A[0]
for i = 1 to 9
	if (A[i] > max) max = A[i]
return max

2-3. 플로차트(flow chart)로 표현된 알고리즘

매우 제한적으로 사용

3. 알고리즘의 효율성 표현

알고리즘의 수행 시간 또는 알고리즘이 수행하는 동안 사용 되는 메모리 공간의 크기로 나타낼 수 있다. 이들을 각각 시간복잡도(time complexity), 공간복잡도(space complexity)라고 한다. 일반적으로 알고리즘들을 비교할 때에는 시간복잡도가 주로 사용된다.

컴퓨터에서 수행된 시간을 측정할 수 있지만, 실제 측정된 시간은 여러 가지 변수가 있다.(컴퓨터의 성능, 프로그래밍의 언어, 최적화 등등) 따라서, 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현한다.

예를 들어, 10장의 숫자 카드에서 최대 숫자를 찾을 때, 비교연산은 총 9번(n-1)이다. 따라서 시간복잡도는 (n-1)이다.

효율성 표현

• 공간복잡도 (space complexity) : 극히 제한적인 문제(merge sort) 같은 문제에서나 사용됨
• 시간복잡도 (time complexity)
  • 최악 경우 분석 (worst case analysis) : '어떤 입력이 주어지더라도 얼마 이상을 넘지 않는다'라는 표현
  • 평균 경우 분석 (average case analysis) : 입력이 확률 분포가 균등 분포 (uniform distribution)이라 가정한다. 즉, 입력이 무작위로 주어진다고 가정한다. 
  • 최선 경우 분석 (best case analysis) : 최적(optimal) 알고리즘을 고안하는데 참고 자료로 활용 즉, 이보다 성능이 우수한 알고리즘은 없다.

4. 복잡도의 표기

시간(또는 공간) 복잡도는 입력 크기에 대한 함수로 표기, 주로 여러 개의 항을 가지는 다항식이다. 이를 단순한 함수로 표현하기 위해 점근적 표기(asymptotic notation)를 사용한다. 이는 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법이다.

예를 들어보자

$ 3n^3 -15n^2+10n-18$ 을 $n^3$으로, $2n^2-8n+3$을 $n^2$으로, $4n+6$을 $n$으로 단순화시킨다. 즉, 다항식의 최고차항만을 계수 없이 취한 것이다. 이 식에 상한, 하한, 동일한 증가율과 같은 개념을 적용하여, 점근적 표기를 사용한다.

4.1 점근적 표기

• $O$(Big-Oh)-표기 : 복잡도의 점근적 상한을 나타냄
• $\Omega$(Big-Omega)-표기 : 복잡도의 점근적 하한을 나타냄
• $\theta$(Theta)-표기 : 복잡도의 상한과 하한이 동시에 적용됨을 나타냄

$O$(Big-Oh)-표기

O-표기는 복잡도의 점근적 상한 이라는 것을 예제를 통해 살펴보자

$f(n) = 2n^2-8+3$ 이라면, $f(n)$ 의 $O$ -표기는 $O(n^2)$이다.

-> 단순화한 함수 $n^2$에 임의의 상수 c를 곱한 $cn^2$이 $n$이 증가함에 Ekfk $f(n)$의 상한이 된다. 단, $c>0$

    $O$-표기에는 c가 '숨겨져 있다'라고 생각해도 좋다.

$\Omega$(Big-Omega)-표기 

$\Omega$(Big-Omega)-표기는 점근적 하한이라는 것을 예제를 통해 살펴보자

$f(n) = 2n^2-8+3$ 이라면, $f(n)$ 의 $\Omega$ -표기는 $O(n^2)$이며 '$n$이 증가함에 따라 $2n^2-8n+3$이 $cn^2$보다 작을 수  없다는 의미이다. 상수 $c$ = 1 로 놓으면 된다. 위와 마찬가지로 최고차항만 계수 없이 취하면 된다.

$\theta$(Theta)-표기

$\theta$(Theta)-표기는 복잡도가 위의 2개와 같은 경우에 사용한다. 즉, '$f(n)은 $n$이 증가함에 따라 $n^2$과 동일한 증가율을 가진다

4.2 시간복잡도 표기

• $O(1)$              상수 시간 (constant time) 
• $O(logn)$         로그(대수) 시간 (logarithmic time)
• $O(n)$              선형 시간 (linear time)
• $O(nlogn)$       로그 선형 시간 (log-linear time)
• $O(n^2)$          이차 시간 (quadratic time)
• $O(n^3)$          3차 시간 (cubic time)
• $O(2^n)$          지수 시간 (exponential time)
• $O(n!)$            

https://www.acmicpc.net/problem/3187

문제

입력

출력

풀이방법

방법은 BFS로 풀었습니다.

 . , v, k 로 이루어진 블럭을 BFS로 찾습니다. 블럭안에 v와 k의 크기의 따라  k  > v 면 k, 0 을 반환하고 k <= v 면 0, v 를 반환하여 총합을 반환합니다.

코드

from collections import deque
import sys

input = sys.stdin.readline

r, c = map(int , input().rstrip().split())

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(i, j):
    w, s = 0, 0
    visited[i][j] = True
    deq = deque([(i,j)])
    while deq:
        x, y = deq.popleft()
        if matrix[x][y] == 'k':
            s += 1
        if matrix[x][y] == 'v':
            w += 1
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < r and 0<= ny < c and visited[nx][ny] == False and matrix[nx][ny] != '#':
                deq.append((nx,ny))
                visited[nx][ny] = True
    if s > w:
        w = 0
    else:
        s = 0
    return w, s



matrix = [list(list(input().rstrip())) for _ in range(r)]
visited = [[False] * c for _ in range(r)]

total_w, total_s = 0, 0
for i in range(r):
    for j in range(c):
        if matrix[i][j] != '#' and visited[i][j] == False:
            w,s = bfs(i,j)
            total_w += w
            total_s += s
print(total_s, total_w)

https://school.programmers.co.kr/learn/courses/30/lessons/131127

문제

입출력( + 추가적인 Test Case)

제한사항

풀이방법

유저의 쇼핑목록과 개수를 Counter class 로 구성합니다.

1일차부터 n, len(discount)-9 일까지의 각각의 카운터를 구성합니다.

만약 user_counter 와 mart_counter가 동일하다면 answer 을 1씩 더합니다.

마지막 answer을 반환합니다.

코드

from collections import Counter

def solution(want, number, discount):
    answer = 0
    user = dict()
    for i in zip(want,number):
        user[i[0]] = i[1]
    user_counter = Counter(user)
    for i in range(0,len(discount)-sum(number)+1):
        mart = Counter(discount[i:i+10])
        if user_counter == mart:
            answer += 1
    return answer

https://www.acmicpc.net/problem/17069

문제 및 입출력 

풀이방법

처음의 파이프는 이와 같이 가로로 되어 있습니다. 

입력받은 N x N 의 DP행렬을 생성합니다. 각각의 행렬안에는 크기가 3인 배열이 있으며 각각 대각선, 세로, 가로입니다.

* 입력받은 행렬을 matrix로 표현합니다.

이후 DP[i][j]의 칸의 값을 구하는 방법은 다음과 같습니다.

(대각선)

matrix[i-1][j-1], matrix[i-1][j], matrix[i][j-1]의 칸이 모두 0인 경우 (모두 벽이 아닌 빈칸)

DP[i][j][0] = sum(DP[i-1][j-1])

(세로)

matrix[i-1][j-1] 이 0인 경우(벽이 아닌 빈칸)

현재칸의 세로 파이프 = 위칸에서의 대각선으로 들어온 파이프 + 위칸에서의 세로로 들어온 파이프

dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j][1]

(가로)

matrix[i-1][j-1] 이 0인 경우(벽이 아닌 빈칸)

현재칸의 가로 파이프 = 왼쪽칸에서의 대각선으로 들어온 파이프 + 왼쪽칸에서의 가로로 들어온 파이프

dp[i][j][2] = dp[i][j-1][0] + dp[i][j-1][2]

코드

import sys

# 입력
N = int(input())
matrix = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)]
# 대각선, 세로, 가로
dp = [[[0] * 3 for _ in range(N+1)] for __ in range(N+1)]
dp[1][2][2] = 1
for i in range(1,N+1):
    for j in range(3, N+1):
        if matrix[i-1][j-1] == 0:
            # 대각선
            if matrix[i-1][j-2] == 0 and matrix[i-2][j-1] == 0:
                dp[i][j][0] = sum(dp[i-1][j-1])
            # 세로
            dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j][1]
            # 가로
            dp[i][j][2] = dp[i][j-1][0] + dp[i][j-1][2]

print(sum(dp[N][N]))

결론

처음의 초기값을 잘 주는 것을 성공적으로해서 생각보다 빨리 풀 수 있었습니다.

마지막 DP배열을 증가시키는 과정에서 다른 방법을 쓰면 DP배열을 확장하지 않아도 될 것 같지만 코드의 가독성을 위해 썼습니다.

https://www.acmicpc.net/problem/15992

문제

입출력 보기

풀이방법

m = 수의 합, n = 사용한 수의 개수

왼쪽의 표를 보게 되면 형광색으로 칠한 것의 합이 빨간색 화살표로 가리킨 숫자와 같습니다.

그 이유는 오른쪽의 한 예시를 보면 알 수 있습니다. 

예시) f(4,2)에서  1 + 3, 2 + 2, 3 + 1 이렇게 3개의 숫자입니다. 이 숫자들은 각각 1, 2, 3에 3, 2, 1를 더한 것입니다.

이 예시를 통해 정리한 식은 우하단의 식과 같습니다.

f(m, n) = f(m-1, n-1) + f(m-2, n-1) + f(m-3, n-1) -> 각각의 수들에서 1, 2, 3을 더한 수들의 합이라고 보시면 됩니다. 

코드

import sys

input=sys.stdin.readline
MAX = 1001
MOD = 1_000_000_009

# 초기값 설정
dp = [[0] * MAX for _ in range(MAX)]
dp[1][1] = 1
dp[2][1], dp[2][2] = 1,1
dp[3][1], dp[3][2], dp[3][3] = 1, 2, 1

for i in range(4, MAX):
    for j in range(1, i + 1):
        dp[i][j] = (dp[i-1][j-1] + dp[i-2][j-1] + dp[i-3][j-1]) % MOD

# 출력
N = int(input())
for i in range(N):
    n, m = map(int, input().split())
    print(dp[n][m])

문제

입출력( + 추가적인 Test Case)

제한사항

풀이방법

1. 완호의 점수를 저장해놓습니다.

2. 점수를 근무 태도 점수는 내림차순, 동료 평가 점수는 오름차순으로 정렬합니다.

3. 현재 점수가 완호의 점수보다 모두 크다면 -1을 반환합니다.

4. limit > score[1]인 경우, incentive를 받지 못하는 사람이므로 다음 차례로 넘어갑니다.

5. limit <= score[1]인 경우, incentive를 받는 사람이므로 완호의 점수의 총합과 비교해서 등수를 계산합니다.

6. limit을 갱신합니다.

7. 비교가 끝나면 등수를 반환합니다.

* limit > score[1]일 때, incentive를 받지 못하는 이유에 대해 설명해보겠습니다.

limit은 이전 수들 중에서 가장 큰 동료 평가 점수(score[1])입니다.

현재 동료 평가 점수(socre[1])가 limit 보다 작다면, 동료의 인사고과 점수보다 낮은 것을 알 수 있습니다.

현재 근무 태도 점수(socre[0])은 내림차순입니다. 다시 말한다면, 이전 동료의 근무 태도 점수가 더 높다는 것입니다.

다시말해서, score[0], score[1] 모두 동료의 점수보다 낮다는 것을 알 수 있습니다.

코드

def solution(scores):
    answer = 1
    wanho_score = scores[0]
    sum_wanho_score = sum(scores[0])
    scores.sort(key=lambda x: (-x[0], x[1]))
    limit = 0

    for score in scores:
        sum_score = sum(score)
        if wanho_score[0] < score[0] and wanho_score[1] < score[1]:
            return -1

        # limit > score[1] 은 incentive를 받지 못하는 사람이다.
        if limit <= score[1]:

            # 성립한다는 것은 인센티브를 받는 것이므로 숫자를 계산해서 등수를 계산한다.
            if sum_wanho_score < sum_score:
                answer += 1
            limit = score[1]
    return answer

결론

처음에 문제를 잘못 해석해 시간이 오래 걸렸다. 10번 줄에 max(wanho_score) < min(score)인 경우로 계산했는데 이 것은 틀린 풀이이다. 두 값 중 min과 max를 구하는 것이 아닌 각각의 요소의 대소관계를 계산했어야 했다. 그 이후 오름차순과 내림차순을 떠올리지 못해서 다른 분들의 코드를 참고해서 문제를 풀었다. Level 3으로 와서 그런지 문제가 상당히 어렵다.

https://school.programmers.co.kr/learn/courses/30/lessons/160585

문제

입출력( + 추가적인 Test Case)

제한사항

풀이방법

틱택토가 성립이 안되는 경우가 있습니다.

1. 순서가 어긋난 경우

2. X가 성립되고 O를 놓는 경우

3. O가 성립되고 X를 놓는 경우

총 3가지가 있습니다.

1번의 경우

O의 개수는 cnt_o, X의 개수는 cnt_X 입니다.

cnt_x > cnt_o 의 경우

cnt_o > cnt_x + 1 의 경우 2가지 중 하나라도 성립되는 경우 오류입니다.

tic_o는 O가 성립된 경우, tic_x는 X가 성립된 경우 입니다.

2번의 경우

tic_x == 1 이면서 cnt_o > cnt_x 이면, X가 성립되고 O를 놓은 경우이므로 오류입니다.

3번의 경우

tic_o == 1 이면서 cnt_o == cnt_x 이면, O가 성립되고, X를 놓는 경우이므로 오류입니다.

총 3가지의 경우를 거치고 오류가 없다면 틱택토는 성립합니다.

코드

def tic_tac_toe(player, board):
    tic = 0

    for i in range(3):
        if all(player == cell for cell in board[i]):
            tic += 1

    for j in range(3):
        if all(player == board[i][j] for i in range(3)):
            tic += 1

    if all(board[i][i] == player for i in range(3)):
        tic += 1
    if all(board[i][2 - i] == player for i in range(3)):
        tic += 1

    return tic


def solution(board):
    board_list = [list(i) for i in board]

    # x, o 개수 세기
    cnt_x, cnt_o = 0, 0
    for i in range(3):
        for j in range(3):
            if board_list[i][j] == 'X':
                cnt_x += 1
            elif board_list[i][j] == 'O':
                cnt_o += 1
            else:
                continue

    # 순서가 어긋난 경우
    if cnt_x > cnt_o or cnt_o > cnt_x + 1:
        return 0
        
	# x와 o의 틱택토 성립하는지 확인
    tic_o = tic_tac_toe('O', board)
    tic_x = tic_tac_toe('X', board)

    # o 가 완성된 이후 x를 놓은 경우
    if tic_o == 1 and (cnt_x == cnt_o):
        return 0

    # x 가 완성된 이후 o를 놓은 경우
    if tic_x == 1 and (cnt_o > cnt_x):
        return 0

    return 1

all functions을 사용하지 않은 경우

def tic_tac_toe(board_list):
    tic_o = 0
    if board_list[0] == ['O', 'O', 'O'] or board_list[1] == ['O', 'O', 'O'] or board_list[2] == ['O', 'O', 'O']:
        tic_o += 1

    if board_list[0][0] == 'O' and board_list[1][0] == 'O' and board_list[2][0] == 'O':
        tic_o += 1
    elif board_list[0][1] == 'O' and board_list[1][1] == 'O' and board_list[2][1] == 'O':
        tic_o += 1
    elif board_list[0][2] == 'O' and board_list[1][2] == 'O' and board_list[2][2] == 'O':
        tic_o += 1

    if board_list[0][0] == 'O' and board_list[1][1] == 'O' and board_list[2][2] == 'O':
        tic_o += 1
    elif board_list[0][2] == 'O' and board_list[1][1] == 'O' and board_list[2][0] == 'O':
        tic_o += 1

    tic_x = 0
    if board_list[0] == ['X', 'X', 'X'] or board_list[1] == ['X', 'X', 'X'] or board_list[2] == ['X', 'X', 'X']:
        tic_x += 1

    if board_list[0][0] == 'X' and board_list[1][0] == 'X' and board_list[2][0] == 'X':
        tic_x += 1
    elif board_list[0][1] == 'X' and board_list[1][1] == 'X' and board_list[2][1] == 'X':
        tic_x += 1
    elif board_list[0][2] == 'X' and board_list[1][2] == 'X' and board_list[2][2] == 'X':
        tic_x += 1

    if board_list[0][0] == 'X' and board_list[1][1] == 'X' and board_list[2][2] == 'X':
        tic_x += 1
    elif board_list[0][2] == 'X' and board_list[1][1] == 'X' and board_list[2][0] == 'X':
        tic_x += 1

    return tic_o, tic_x


def solution(board):
    board_list = [list(i) for i in board]

    # x, o 개수 세기
    cnt_x, cnt_o = 0, 0
    for i in range(3):
        for j in range(3):
            if board_list[i][j] == 'X':
                cnt_x += 1
            elif board_list[i][j] == 'O':
                cnt_o += 1
            else:
                continue

    # 순서가 어긋난 경우
    if cnt_x > cnt_o or cnt_o > cnt_x + 1:
        return 0

    tic_o, tic_x = tic_tac_toe(board_list)

    # o 가 완성되었는데 x를 놓은 경우
    if tic_o == 1 and (cnt_x == cnt_o):
        return 0

    # x 가 완성되었는데 o를 놓은 경우
    if tic_x == 1 and (cnt_o > cnt_x):
        return 0

    answer = 1
    return answer

결론

처음에 규칙을 찾느라 어려웠다. 틱택토를 해본적도 없었기 때문이다. 규칙을 빨리 찾고나서 구현은 생각보다 쉬웠다. 하지만 밑에 있는 코드는 너무 복잡해 보여서 Python의 all function을 사용해서 깔끔하게 바꾸었다. 덕분에 all function을 배워갔다.

https://school.programmers.co.kr/learn/courses/30/lessons/159993

문제

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

입출력( + 추가적인 Test Case)

제한사항에 대해 보고싶으면 눌러주세요

풀이방법

사용한 알고리즘 : BFS

크게 2개로 나누어서 구현했습니다.

1. S 에서 L까지의 최단거리를 구합니다.

2. L 에서 E까지의 최단거리를 구합니다.

-> 최단거리를 구하는 방식은 BFS를 사용해서 풀었습니다.

코드

from collections import deque

INF = float('inf')

def solution(maps):
    answer = 0
    n = len(maps)
    m = len(maps[0])
    matrix = [[INF] * m for _ in range(n)]
    deq = deque()
    
    # S 위치 찾기
    for i in range(n):
        for j in range(m):
            if maps[i][j] == 'S':
                matrix[i][j] = 0
                deq.append((i, j, 0))
                break
        if deq:
            break

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

    # S => L
    while deq:
        x, y, cnt = deq.popleft()

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

            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] != 'X':
            
            	# L을 찾았을 경우
                if maps[nx][ny] == 'L':
                    answer += cnt + 1

                    # deq 초기화
                    deq = deque()
                    deq.append((nx, ny, 0))
                    break
                    
                if cnt + 1 < matrix[nx][ny]:
                    matrix[nx][ny] = cnt + 1
                    deq.append((nx, ny, cnt + 1))
        if answer != 0:
            break

    temp_answer = answer
    matrix = [[INF] * m for _ in range(n)]

    # L => E
    
    while deq:
        x, y, cnt = deq.popleft()

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

            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] != 'X':
                if maps[nx][ny] == 'E':
                    answer += cnt + 1
                    break
                if cnt + 1 < matrix[nx][ny]:
                    matrix[nx][ny] = cnt + 1
                    deq.append((nx, ny, cnt + 1))
        
        # answer 값이 변하면 break
        if answer != temp_answer:
            break

	# L -> E 경로가 없으면 -1
    if answer == temp_answer:
        return -1

    return answer

결론

1. S 에서 L까지의 최단거리를 구합니다.

2. L 에서 E까지의 최단거리를 구합니다.

1에서 최단거리가 없을 경우, 2에서 최단거리가 없는 경우와 둘 다 없는 경우를 생각해서 풀면 바로 풀리는 문제이다. 단, 범위오류가 발생할 수 있으니 변수 설정을 잘 해주면 된다.

처음 겪어보는 런타임 에러여서 당황했지만 백준에서 해왔던 것처럼 범위 오류라 가정하고 변수를 재설정하여 해결하였다.