문제
아래 그림과 같은 미로가 있다. 100*100 행렬의 형태로 만들어진 미로에서 흰색 바탕은 길, 노란색 바탕은 벽을 나타낸다.
가장 좌상단에 있는 칸을 (0, 0)의 기준으로 하여, 가로방향을 x 방향, 세로방향을 y 방향이라고 할 때, 미로의 시작점은 (1, 1)이고 도착점은 (13, 13)이다.
주어진 미로의 출발점으로부터 도착지점까지 갈 수 있는 길이 있는지 판단하는 프로그램을 작성하라.
아래의 예시에서는 도달 가능하다.
아래의 예시에서는 출발점이 (1, 1)이고, 도착점이 (11, 11)이며 도달이 불가능하다.
위의 예시는 공간상의 이유로 100x100이 아닌 16x16으로 주어졌음에 유의한다.
[입력]
각 테스트 케이스의 첫 번째 줄에는 테스트케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.
총 10개의 테스트 케이스가 주어진다.
테스트 케이스에서 1은 벽을 나타내며 0은 길, 2는 출발점, 3은 도착점을 나타낸다.
[출력]
#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 도달 가능 여부를 1 또는 0으로 표시한다 (1 - 가능함, 0 - 가능하지 않음).
풀이
1226 미로1와 같다.
16X16의 미로크기를 100X100으로 변경만 해주면 끝.
미로1의 풀이는 여기 -> SWEA 1226 - 미로1
코드
search = [[-1, 0], [1, 0], [0, -1], [0, 1]]#상하좌우
for _ in range(10):
test_case = int(input())
maze = []
stack = []
result = 0
#미로 만들기
for _ in range(100):
a = input()
temp = []
for j in range(100):
temp.append(int(a[j]))
maze.append(temp)
#시작점 넣기
stack.append([1, 1])
while stack:
now_y, now_x = stack.pop()
if maze[now_y][now_x] == 3: #도착하면 while종료
result = 1
break
#현재 있는곳 방문했다고 표시
maze[now_y][now_x] = 1
for coordinate in search: #상하좌우 뒤지기
temp_y, temp_x = coordinate
y = now_y + (temp_y)
x = now_x + (temp_x)
if maze[y][x] != 1: #갈수있는 곳이면 stack에 저장!
stack.append([y, x])
print(f'#{test_case} {result}')
SW Engineer