SWEA 1210 사다리타기

🏸문제

---

💊풀이

dfs 를 활용하여 2차원 배열을 탐색하자!

1. 주어진 배열의 마지막 행에서 2를 찾는다.
2. 2에서 좌, 우로 이동할 수 있으면 이동하며 가장 먼저 도착하는 첫번째 행의 1을 찾아낸다.
3. 첫번재 행의 1을 찾으면 모든 재귀를 종료시킨다.

---

📌코드

import sys
sys.stdin = open('input.txt')

# 0:좌, 1:우, 2:상
d = [(-1,0),(1,0),(0,-1)]

def find_two(arr)->tuple:
    num = 0
    for idx in arr[-1][:]:
        if idx == 2:
            return (99, num)
        num += 1

def get_start_point(r,c)->int:
    for i in range(3):
        nr = r+d[i][1]  # 위로 올라가기
        nc = c+d[i][0]  # 좌, 우 탐색
        if 0 <= nr <= 99 and 0 <= nc <= 99 and arr[nr][nc] == 1:    # 탐색 범위 조건
            if nr == 0 and arr[nr][nc] == 1:
                print( f'#{tc} {nc}')   # 사다리의 시작점을 찾으면 재귀 정답 출력
            arr[nr][nc] = 0 # 이미 지나온 길은 0으로 바꾸어 다시 못지나가게
            return get_start_point(nr, nc) # return 으로 재귀를 호출해서 조건을 만족하는 값 하나를 찾으면 다른 재귀는 호출하지 않고 전부 종료

for _ in range(10):
    tc = int(input()) # tc 받기
    arr = [list(map(int, input().split())) for _ in range(100)] # 사다리를 표시하는 2차원 배열 받기
    end_point = find_two(arr)   # 사다리가 끝나는 지점인 2의 위치 찾기
    get_start_point(end_point[0], end_point[1]) # 2에서 시작 지점으로 찾아서 올라가기

---

🛀결과

엄청 오랜만에 알고리즘을 풀려니 생각보다 힘들었다. 과거에 가장 기초 문제로 풀었던 것부터 시작했는데도 input을 받는 방법도 잘 기억이 나지 않았고 dfs 탐색 방법도 구현이 잘 되지 않았다. 또한 dfs를 구현 후에 조건을 만족했을 때 모든 재귀를 종료시키는 방법도 잘 떠오르지 않아 생각보다 고전하였다. 이제부터는 다시 매일 한 문제씩 풀어가며 알고리즘 수준을 높여보자!!! 화이팅!

(알고리즘이 쉬워지는 날까지 열심히!)