[김태원 알고리즘] 사다리 타기 (DFS)

사용 언어: Python3

문제

풀이

내 풀이

import sys
sys.setrecursionlimit(10**6)

dx, dy = [0,0,1], [1,-1,0] # ✅ 위로는 안감 (위쪽 제외)
def DFS(x, y):
    global path, isCurved
    if isCurved:
        return
    visited[x][y] = 1
    path.append((x, y))
    if board[x][y] == 2: # ✅ 도착지점까지 path에 담고 return
        return
    for w in range(3):
        xx, yy = x+dx[w], y+dy[w]
        if xx<0 or xx>=N or yy<0 or yy>=N:
            continue
        if board[xx][yy] == 0 or visited[xx][yy]:
            continue
        DFS(xx, yy)
        isCurved = True # ✅ 꺾었다면 아래쪽으로는 가지 않기 위해
        
N = 10
board = [list(map(int, input().split())) for _ in range(N)]

for i in range(N):
    visited = [[0] * N for _ in range(N)] # ✅ 매 열에서 출발할 때 visited 리셋
    if board[0][i] == 0 or visited[0][i]:
        continue
    path = [] # ✅ 매 DFS 전 경로 초기화
    isCurved = False # ✅ 매 DFS 전 꺾었는지 담아두는 플래그 초기화
    DFS(0, i)
    if board[path[-1][0]][path[-1][1]] == 2: # 도착 지점 값이 2 라면
        print(path[0][1]) # 출발 지점의 열 출력
        break

내 풀이 - 도착 지점이 2인 지점부터 역으로 출발

import sys
sys.setrecursionlimit(10**6)

dx, dy = [0,0,-1], [1,-1,0] # ✅ 아래로는 안감 (아래쪽 제외) # 순회 순서는 좌/우 먼저 위는 나중
def DFS(x, y):
    global isCurved
    if isCurved:
        return
    if x == 0: # ✅ 출발지점(0행)에 도착했다면
        print(y) # 열 번호 출력
        return
    visited[x][y] = 1
    for w in range(3):
        xx, yy = x+dx[w], y+dy[w]
        if xx<0 or xx>=N or yy<0 or yy>=N:
            continue
        if board[xx][yy] == 0 or visited[xx][yy]:
            continue
        visited[xx][yy] = 1
        DFS(xx, yy)
        isCurved = True
        
N = 10
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[0] * N for _ in range(N)]
isCurved = False

for i in range(N):
    if board[N-1][i] == 2: # ✅ 도착지점부터 출발
        DFS(N-1, i)

• 역으로 출발하면 더욱 간단해지고 path를 저장할 필요도 없다.
  • visited와 isCurved도 반복마다 초기화하는 것이 아니라 하나로 사용 가능하다!

다른 풀이 - isCurved 플래그 사용 X

import sys
sys.setrecursionlimit(10**6)

def DFS(x, y):
    visited[x][y] = 1
    if x == 0: # 출발지점(0행)에 도착했다면
        print(y) # 열 번호 출력
    else: # ✅ for문이 아니라 if~else로 하면 하나의 DFS만 타고간다 (단, 위보다 좌/우가 먼저)
        if y-1 >= 0 and board[x][y-1] == 1 and not visited[x][y-1]: # 왼쪽
            DFS(x, y-1)
        elif y+1 < N and board[x][y+1] == 1 and not visited[x][y+1]: # 오른쪽
            DFS(x, y+1)
        elif x-1 >= 0 and board[x-1][y] == 1 and not visited[x-1][y]: # 위쪽
            DFS(x-1, y)
        
N = 10
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[0] * N for _ in range(N)]

for i in range(N):
    if board[N-1][i] == 2:
        DFS(N-1, i)

• 🌟 for문 대신에 if~else를 사용하면 세 방향 중 하나의 DFS만 타고가기 때문에 isCurved를 사용할 필요가 없다!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기