[Python] [HSAT 7회 정기 코딩 인증평가 기출] 순서대로 방문하기

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

https://softeer.ai/practice/6246

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

 

문제 해결 과정

- '순서가 있는 방문 루트 구하기'라고 인지하자마자  DFS(깊이 우선 탐색)임을 인지했다.

- 방문 표시를 위한 visited 배열이 필요함을 떠올렸다.

 

- 현재 위치를 기준으로 상하좌우를 보았을 때

   1) 유효한 공간( 0 ~ n-1 )을 벗어나지 않고

   2) 방문하지 않았고

   3) 벽이 아닌

 

- 순서를 지키고 있는가?

  첫시도) 방문할 위치가 지나야할 위치 리스트에 포함되는데, 순서가 맞지 않을 때 해당 루트는 더이상 탐색하지 않는다

 

=> 첫시도에서 문제가 되었던 것은 잘못 된 문법의 사용과 복잡하고 구멍 뚫린 조건문 때문이다.

if (row, col) in points:
    if not points[depth-1] != (row, col):
        continue
    else:
        visited[row][col] = True
        dfs(row, col, depth+1)

 

1. `(row, col) in points`:

• 이 조건은 현재 탐색 중인 (row, col) 좌표가 points 리스트에 포함되어 있는지를 확인합니다.
• points 리스트는 방문해야 할 체크포인트들의 좌표를 저장한 리스트입니다.
• 이 조건이 참이면, row와 col이 체크포인트 중 하나라는 의미

2. `if not points[depth-1] != (row, col)`:

• depth가 나타내는 것은 다음 방문해야할 체크포인트 순서를 의미한다.
• 그러므로 depth-1로 이전 방문한 체크포인트를 확인할 것이 아니라 depth의 체크포인트 위치를 확인해야한다.

 

  재시도) 방문할 위치가 다음 지나야할 순서에 부합한다면 depth+1로 dfs, 부합하지 않는다면 depth로 dfs

 

- 반성 : 괜한 가지치기를 시도하였다가 구멍 뚫린 조건문을 실행하지 말고 완탐을 수행하고 추가 조건을 달아나가는 방식을 선택하자.

 

작성 코드

실패 코드

import sys
input = sys.stdin.readline

# 격자의 크기, 방문 포인트 개수
n, m = map(int, input().split())

# n개의 수
board = []
for i in range(n):
    board.append(list(map(int, input().split())))

# 방문해야 할 m개의 칸의 위치(x, y)
points = []
for i in range(m):
    x, y = map(int, input().split())
    points.append((x-1, y-1))

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
visited = [[False]*n for _ in range(n)]
answer = 0

def dfs(r, c, depth):
    global answer
    if depth == m:
        answer += 1
        return

    for d in range(4):
        row = r + dr[d]
        col = c + dc[d]
        if -1 < row < n and -1 < col < n and not board[row][col] and not visited[row][col]:
            if (row, col) in points:
                if not points[depth-1] != (row, col):
                    continue
                else:
                    visited[row][col] = True
                    dfs(row, col, depth+1)
            else:
                visited[row][col] = True
                dfs(row, col, depth)
            visited[row][col] = False
    
visited[points[0][0]][points[0][1]] = True
dfs(points[0][0], points[0][1], 1)
print(answer)

 

성공 코드

import sys
input = sys.stdin.readline

# 격자의 크기, 방문 포인트 개수
n, m = map(int, input().split())

# n개의 수
board = []
for i in range(n):
    board.append(list(map(int, input().split())))

# 방문해야 할 m개의 칸의 위치(x, y)
points = []
for i in range(m):
    x, y = map(int, input().split())
    points.append((x-1, y-1))

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
visited = [[False]*n for _ in range(n)]
answer = 0

def dfs(r, c, depth):
    global answer
    if depth == m:
        answer += 1
        return
    elif (r, c) == points[-1]:
        return

    for d in range(4):
        row = r + dr[d]
        col = c + dc[d]
        if -1 < row < n and -1 < col < n and not board[row][col] and not visited[row][col]:
            visited[row][col] = True
            if points[depth] == (row, col):
                dfs(row, col, depth+1)
            else:
                dfs(row, col, depth)
            visited[row][col] = False
    
visited[points[0][0]][points[0][1]] = True
dfs(points[0][0], points[0][1], 1)
print(answer)

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚