문제 설명
•
행렬의 형태로 만들어진 미로에서 탈출 가능 여부를 구하는 문제
◦
행렬에서 0은 길, 1은 벽, 2는 출발점, 3은 도착점을 의미
◦
탈출이 가능하다면 1, 불가능하다면 0을 출력
예제 입력/출력
•
입력1
1
1111111111111111
1210000000100011
1010101110101111
1000100010100011
1111111010101011
1000000010101011
1011111110111011
1010000010001011
1010101111101011
1010100010001011
1010111010111011
1010001000100011
1011101111101011
1000100000001311
1111111111111111
1111111111111111
...
Plain Text
복사
•
출력1
#1 1
...
Plain Text
복사
제약 조건
•
◦
은 행렬의 크기
문제 풀이
•
DFS -
◦
너비 우선 탐색(BFS) 혹은 깊이 우선 탐색(DFS)을 이용해 문제를 풀 수 있다.
◦
이 문제는 최단 경로가 아닌, 단순히 탈출 여부만을 구하면 되기 때문에 DFS를 사용하여 문제를 풀었다.
풀이 코드
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def dfs(x, y):
if matrix[y][x] == 3: # 도착 지점 확인
return 1
visited[y][x] = True
for d in range(4):
nx, ny = x + dx[d], y + dy[d]
if (0 <= nx < N) and (0 <= ny < N) and not visited[ny][nx] and matrix[ny][nx] != 1:
if dfs(nx, ny): # 경로가 있으면 1을 반환
return 1
return 0 # 경로가 없으면 0을 반환
T = 10
for _ in range(1, T + 1):
tc = int(input())
N = 16
matrix = [list(map(int, input())) for _ in range(N)]
# 시작점과 방문 배열 초기화
ans = 0
visited = [[False] * N for _ in range(N)]
ans = dfs(1, 1)
print(f"#{tc} {ans}")
Python
복사