[파이썬] 1226. 미로1

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

아래 그림과 같은 미로가 있다. 16*16 행렬의 형태로 만들어진 미로에서 흰색 바탕은 길, 노란색 바탕은 벽을 나타낸다.

가장 좌상단에 있는 칸을 (0, 0)의 기준으로 하여, 가로방향을 x 방향, 세로방향을 y 방향이라고 할 때, 미로의 시작점은 (1, 1)이고 도착점은 (13, 13)이다.

주어진 미로의 출발점으로부터 도착지점까지 갈 수 있는 길이 있는지 판단하는 프로그램을 작성하라.

아래의 예시에서는 도달 가능하다.

 

 

아래의 예시에서는 출발점이 (1, 1)이고, 도착점이 (11, 11)이며 도달이 불가능하다.

 

 

[입력]

각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.

총 10개의 테스트케이스가 주어진다.

테스트 케이스에서 1은 벽을 나타내며 0은 길, 2는 출발점, 3은 도착점을 나타낸다.

[출력]

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 도달 가능 여부를 1 또는 0으로 표시한다 (1 - 가능함, 0 - 가능하지 않음).

 

입력

너무 길어서 생략.

직접 SW expert academy에서 찾기

 

출력

#1 1

#2 1

...

 

 

 

🎀 나의 풀이

def dfs(x, y):
    global temp
    temp=0
    
    if visited[x][y] == 0 and maze[x][y] != '1' :		# 방문한 적 없고 길 있으면
        if maze[x][y] == '3' :	# 도착
            return 1
        visited[x][y]=1			# 방문 처리
        # 4방향으로 재귀호출
        temp+=dfs(x-1, y)		
        temp+=dfs(x+1, y)
        temp+=dfs(x, y-1)
        temp+=dfs(x, y+1)  
        return temp
    else:
        return 0		# 미로 탈출 못 함
        
for test_case in range(10):		# 10개의 테스트 케이스
    T=input()		# 테스트 케이스 번호
    maze=[[1]*16 for _ in range(16)]	# 16*16 미로(0 : 길, 1 : 벽, 2 : 출발, 3 : 도착)
    visited=[[0]*16 for _ in range(16)]			# 방문기록 
    
    # 미로 입력
    for i in range(16) :
        string=input()
        for j in range(16) :
            maze[i][j]=string[j]
    #출발점
    start_X=1
    start_Y=1
    
    result=dfs(start_X, start_Y)	# 함수 호출
    print(f"#{T} {result}")

 

재귀호출로 구현했다.

 

 

✨ 다른사람 풀이

# 출처 : https://mungto.tistory.com/235

#이동리스트
move_list = [(1, 0), (-1, 0), (0, 1), (0, -1)]
 
def dfs(y, x):
    global result
    #현재 위치가 도착점이라면
    #목표점에 도달했거나 결과가 이미나와있다면 리턴
    if map_list[y][x] == 3 or result:
        result = 1
        return
    for i, j in move_list:
        d_y = y + i
        d_x = x + j
        #반복하다가 결과가 나왔다면 리턴
        if result: 
            return
        #벽이아니거나 왔던 위치가 아니라면
        if map_list[d_y][d_x] != 1 :
            #현재위치를 벽으로 체크하고 재귀
            map_list[y][x] = 1
            dfs(d_y, d_x)			# 재귀호출
        
 
T = 10
for _ in range(T):
    t = int(input())
    N = 16
    map_list = [list(map(int, list(input()))) for _ in range(N)]	# 미로
    result = 0
    #1,1 위치부터 탐색시작
    dfs(1,1)
    print('#{} {}'.format(t, result))

 

같은 dfs지만 방문 처리 리스트가 없다.

미로 만드는 부분이 한 줄로 깔끔하게 작성됨. 리스트 안에 N개의 int형 리스트를 담는다. 

 

# 출처 : https://mungto.tistory.com/235

from collections import deque

# 이동리스트
move_list=[(1, 0), (-1, 0), (0, 1), (0, -1)]

def bfs():
  queue=deque()
  queue.append((1, 1))
  map_list[1][1]=1
  while len(queue) :
    y, x = queue.popleft()
    if map_list[y][x] == 3 :
      return 1
    map_list[y][x]=1		# 방문 표시
    for i in move_list :
      my=i[0]+y
      mx=i[1]+x
      if 0 <= my < N and 0 <= mx < N and map_list[my][mx] != 1 :  # 인덱스 범위 체크와 통행 가능 여부
        queue.append((my, mx))
  return 0		# 도착 실패

for _ in range(10) :
  t=int(input())
  N=16
  map_list=[list(map(int, list(input()))) for _ in range(N)]
  # 1, 1 위치부터 탐색시작
  print('#{} {}'.format(t, bfs()))

 

큐를 이용해서 bfs로 구현함.

 

 

 

문제 출처 SW expert academy