[SWEA][stack] 4875_미로 (211018)

이해도

★★★☆☆

문제

접근방법

[공통]

• 함수에서 이차원 배열과 시작점의 x 및 y 좌표를 파라미터로 사용한다.
• 델타 탐색으로 진행한다.
• 이차원의 visited 배열(0 또는 False)을 만들어 방문처리한다.
• 벽을 빠져나가지 않도록 처리한다.(추가 벽을 세우거나, 델타 범위를 제한한다.)

[다양한 방식]

• 1. DFS 사용
  • 1-1. 스택 사용하여 반복문으로 구현
  • 1-2. 재귀함수로 구현
• 2. DFS 사용하지 않고 구현(스택.pop()대신 좌표를 감소시킴)

 

나의 코드

스택 사용한 반복 DFS 구현

def dfs(board, start):
    visited = [[False] * N for _ in range(N)]
    stack = [start]

    while stack:
        curr = stack.pop()
        visited[curr[0]][curr[1]] = True

        for i in range(4):
            if curr[0] + dr[i] in range(N) and curr[1] + dc[i] in range(N):
                if board[curr[0] + dr[i]][curr[1] + dc[i]] == 3:
                    return True
                if board[curr[0] + dr[i]][curr[1] + dc[i]] == 0 and not visited[curr[0] + dr[i]][curr[1] + dc[i]]:
                    stack.append((curr[0] + dr[i], curr[1] + dc[i]))
    return False


T = int(input())
for tc in range(1, T+1):
    N = int(input())
    board = [list(map(int, input())) for _ in range(N)]

    for r in range(N):
        for c in range(N):
            if board[r][c] == 2:
                start = (r, c)

    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    ans = dfs(board, start)
    print(f"#{tc} {ans}")

 

방법별 코드

1-1. 스택 사용하여 반복문으로 구현 (벽감싸기)

# 벽감싸기 + stack 반복문 활용

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

T = int(input())
for tc in range(1, T + 1):
    N = int(input())
    lst = [[1] * (N + 2)] + [[1] + list(map(int, list(input()))) + [1] for _ in range(N)] + [[1] * (N + 2)]
    for r in range(N + 2):
        for c in range(N + 2):
            if lst[r][c] == 2:
                start = (r, c)
            elif lst[r][c] == 3:
                end = (r, c)

    stack = [start]
    path = [[0] * (N + 2) for _ in range(N + 2)] # visited 역할
    result = 0
    while stack:
        curr = stack.pop()
        path[curr[0]][curr[1]] = 1
        if curr == end:
            result = 1
        # 주위 탐색
        for i in range(4):
            if lst[curr[0] + dx[i]][curr[1] + dy[i]] == 3:  # 주위에 3, 즉 도착점이 있다면 마찬가지로 끝.
                result = 1
            if lst[curr[0] + dx[i]][curr[1] + dy[i]] == 0 and path[curr[0] + dx[i]][curr[1] + dy[i]] == 0:
                stack.append((curr[0] + dx[i], curr[1] + dy[i]))
        # if result == 1:
        #     break

    print('#{} {}'.format(tc, result))

 

1-1. 스택 사용하여 반복문으로 구현2 (상하바꾸기, 불리언 사용)

# boolean 활용
# 상하를 바꾸고 스택을 사용하여 반복문으로 구현

T = int(input())
for tc in range(1, T + 1):

    N = int(input())
    checked = [[0] * N for _ in range(N)]
    board = [list(map(int, list(input()))) for _ in range(N)]

    for i in range(N):
        for j in range(N):
            if board[i][j] == 2:
                start = (i, j)
            elif board[i][j] == 3:
                end = (i, j)
            elif board[i][j] == 1:
                checked[i][j] = 1

    stack = []
    #우하좌상
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    #DFS 구현
    stack = [start]

    boolean = False
    while stack:
        v = stack.pop()
        y = v[0]
        x = v[1]
        checked[y][x] = 1
        if checked[end[0]][end[1]]:
            boolean = True
            break
        #2차원배열 index조건
        for i in range(4):
            if 0 <= y + dy[i] < N and 0 <= x + dx[i] < N and checked[y + dy[i]][x + dx[i]] == 0:
                stack.append((y + dy[i], x + dx[i]))

    #출력
    if boolean:
        print('#{} {}'.format(tc, 1))
    else:
        print('#{} {}'.format(tc, 0))

1-2. 스택없는 재귀 dfs로 구현 (지나간 길은 1로 바꾸어준다.)

# 스택 없는 dfs 재귀로 구현
def dfs(si,sj):
    global result
    for i in range(4):
        if si+di[i] in range(N) and sj+dj[i] in range(N):
            if load[si + di[i]][sj + dj[i]] == 3:
                result = 1
                return
            if load[si + di[i]][sj + dj[i]] == 0:
                load[si + di[i]][sj + dj[i]] = 1
                dfs(si + di[i], sj + dj[i])


for tc in range(1,int(input())+1):
    N = int(input())
    load=[]
    for _ in range(N):
        load.append(list(map(int,input())))

    for i in range(N):
        for j in range(N):
            if load[i][j]==2:
             si,sj=i,j

    di = [0,0,-1,1]
    dj = [1,-1,0,0]
    result = 0
    dfs(si,sj)

    print("#{} {}".format(tc,result))

2. 스택 사용하지않고 반복문과 재귀식만으로 구현 (스택.pop()대신 좌표를 감소시킴)

# 스택없이 반복문과 재귀함수 사용
def check_route(board, cnt_r, cnt_c):

    # 상하좌우 순서로 탐색
    for i in range(4):
        cnt_r += dr[i]
        cnt_c += dc[i]

        # 탐색 위치의 인덱스가 유효하다면
        if 0 <= cnt_r < N and 0 <= cnt_c < N:
            # 도착점을 찾으면 True를 리턴한다.
            if board[cnt_r][cnt_c] == 3:
                return True
            # 현재위치가 0 이고 아직 방문하지 않았다면
            elif (board[cnt_r][cnt_c] == 0 and not visited[cnt_r][cnt_c]):
                # 방문표시하고 해당 위치에서 다시 탐색을 진행한다.
                visited[cnt_r][cnt_c] = True
                if check_route(board, cnt_r, cnt_c):
                    return True
        # 탐색 종료 후에는 기존 위치로 복귀한다.
        cnt_r -= dr[i]
        cnt_c -= dc[i]

    # 탐색을 마쳤는데 도착점을 찾지 못했다면 False를 리턴한다.
    # 재귀함수 였다면, 재귀함수 위치로 돌아간다.
    return False


T = int(input())
for tc in range(1, T+1):
    N = int(input())
    board = [list(map(int, input())) for _ in range(N)]

    # 시작위치 설정
    for i in range(N):
        for j in range(N):
            if board[i][j] == 2:
                cnt_r = i
                cnt_c = j

    # 델타탐색 초기값 설정한다.
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

  	# 방문기록
    visited = [[False] * N for _ in range(N)]

    result = check_route(board, cnt_r, cnt_c)
    print("#{} {}".format(tc, int(result)))

다양한 코드 출처 : SSAFY 6기 서울3반