[softeer level 3] 7차 정기 진단 평가 - 순서대로 방문하기

https://softeer.ai/practice/info.do?idx=1&eid=2050 

Softeer

문제

Sam은 팀장님으로부터 차량이 이동 가능한 시나리오의 수를 찾으라는 업무 지시를 받았습니다. 이동은 숫자 0과 1로만 이루어져 있는 n x n 크기의 격자 위에서 일어납니다. 숫자 0은 빈 칸을 의미하며, 숫자 1은 해당 칸이 벽으로 막혀 있음을 의미합니다. 아래는 n이 3인 경우의 예시입니다.

 

0 0 0
0 0 0
0 0 1

 

차량은 n x n 격자 내에서 m개의 지점을 순서대로 방문하려고 합니다. 이 때 이동은 항상 상하좌우 중 인접한 칸으로만 이동하되 벽은 지나갈 수 없으며, 한 번 지났던 지점은 다시는 방문해서는 안 됩니다. 이러한 조건 하에서 차량이 이동 가능한 서로 다른 가지 수를 구하는 프로그램을 작성해보세요.

 

방문해야 하는 지점의 첫 지점이 출발점이며, 마지막 지점이 도착점임에 유의합니다.

 

위의 예에서 m = 3, 방문해야 하는 지점이 순서대로 (3행, 1열), (1행, 2열), (2행, 3열)이라면, 다음과 같이 5가지의 시나리오가 가능합니다.

 

1. (3행, 1열) → (3행, 2열) → (2행, 2열) → (1행, 2열) → (1행, 3열) → (2행, 3열)

 

2. (3행, 1열) → (3행, 2열) → (2행, 2열) → (2행, 1열) → (1행, 1열) → (1행, 2열) → (1행, 3열) → (2행, 3열)

 

3. (3행, 1열) → (2행, 1열) → (2행, 2열) → (1행, 2열) → (1행, 3열) → (2행, 3열)

 

4. (3행, 1열) → (2행, 1열) → (1행, 1열) → (1행, 2열) → (1행, 3열) → (2행, 3열)

 

5. (3행, 1열) → (2행, 1열) → (1행, 1열) → (1행, 2열) → (2행, 2열) → (2행, 3열)

 

제약 조건

[조건 1] 2 ≤ n ≤ 4

[조건 2] 2 ≤ m ≤ n2

입력 형식

첫 번째 줄에는 격자의 크기를 나타내는 n과 순서대로 방문해야 하는 칸의 수 m이 공백을 사이에 두고 주어집니다.

 

두 번째 줄부터는 n개의 줄에 걸쳐 각 행에 해당하는 n개의 수가 공백을 사이에 두고 주어집니다. 주어지는 수는 0 또는 1이며, 0은 빈 칸을 1은 벽을 의미합니다.

 

n + 2 번째 줄부터는 m개의 줄에 방문해야 할 m개의 칸의 위치 (x, y) 쌍이 공백을 사이에 두고 한 줄에 하나씩 순서대로 주어집니다. 주어지는 칸에 벽이 있는 경우는 없으며, 동일한 칸이 여러 번 주어지는 경우는 없다고 가정해도 좋습니다.

출력 형식

차량이 m개의 지점을 순서대로 방문할 수 있는 서로 다른 방법의 수를 출력합니다. 만약 가능한 방법이 없다면 0을 출력합니다.

입력 예제1

3 3
0 0 0
0 0 0
0 0 1
3 1
1 2
2 3

출력 예제1

5

입력 예제2

3 3
0 0 1
0 0 0
0 0 1
3 1
1 2
2 3

출력 예제2

1

문제 풀이

이 문제는 진단평가에선 BFS로 풀이를 제출했는데 알고 튜터님 풀이를 보니 DFS로 푸셨길래 첨부해본다!

dfs를 탐색하면서 dfs 재귀를 다 돌고나면 방문 처리한 위치는 다시 visited[][]=0으로 방문하지 않은 것으로 처리해줘야 정상적으로 모든 경우의 수를 탐색할 수 있다!

import sys

n,m=map(int, sys.stdin.readline().split(' '))
area=[[0]+list(map(int,sys.stdin.readline().strip().split(' '))) for _ in range(n)]
area.insert(0,[0]*(n+1))
visited=[[0]*(n+1) for _ in range(n+1)]
dest=[]

for i in range(1,m+1):
    y,x=map(int, sys.stdin.readline().strip().split(' '))
    dest.append((y,x))

directions=[(0,1),(1,0),(0,-1),(-1,0)]
ans=0

def dfs(y,x,level):
    global ans
    if (y,x)==dest[level]:
        if level==m-1:
            ans+=1
            return
        else:
            level+=1
    visited[y][x] = 1
    for di in directions:
        dy=y+di[0]
        dx=x+di[1]
        if 1<=dy<=n and 1<=dx<=n and visited[dy][dx]==0 and area[dy][dx]==0:
            dfs(dy,dx,level)
    visited[y][x] = 0

dfs(dest[0][0], dest[0][1], 1)

print(ans)

다음은 내가 푼 BFS 문제 풀이이다.

import sys
from collections import deque

n,m=map(int, sys.stdin.readline().split(' '))

area=[[0]+list(map(int,sys.stdin.readline().strip().split(' '))) for _ in range(n)]
area.insert(0,[0]*(n+1))
visited=[[0]*(n+1) for _ in range(n+1)]
dest=[]

for i in range(1,m+1):
    y,x=map(int, sys.stdin.readline().strip().split(' '))
    dest.append((y,x))

directions=[(0,1),(1,0),(0,-1),(-1,0)]
ans=0

queue=deque()
visited[dest[0][0]][dest[0][1]]=1
queue.append((dest[0][0],dest[0][1],1,visited))
while queue:
    cury, curx, level, visited = queue.popleft()
    if cury==dest[level][0] and curx==dest[level][1]:
        if level==m-1:
            ans+=1
            continue
        else:
            level+=1
    for di in directions:
        dy=cury+di[0]
        dx=curx+di[1]
        if 1<=dy<=n and 1<=dx<=n and visited[dy][dx]==0 and area[dy][dx]==0:
            new_visited = [arr[:] for arr in visited]
            new_visited[dy][dx]=1
            queue.append((dy,dx,level,new_visited))


print(ans)

대신 DFS 풀이와 달리, 매번 큐마다 방문 경로가 저장된 new_visited 배열을 넣어줘야 하기 때문에 n 값이 크다면 메모리 초과가 발생할 확률이 높기 때문에 DFS 풀이가 훨씬 더 좋은 풀이인 것 같다!

 

DFS 풀이의 경우 예제 1번을 기준으로 간략하게 흐름을 그려봤는데 블로그에 포스팅 목적으로 그린 건 아니라서 알아보기 힘들 수 있지만 혹시 도움이 될까해서 올려본다..!