SW Expert Academy - [S/W 문제해결 기본] 7일차 - 미로1
for i in range(10):
tc = int(input())
arr = [list(map(int,input())) for _ in range(16)]
v = [[False]*16 for _ in range(16)]
start_x = 0
start_y = 0
for j in range(len(arr)):
for k in range(len(arr[j])):
if arr[j][k] == 2:
start_x = j
start_y = k
break
# print(start_x,start_y)
dx = [0,0,-1,1]
dy = [-1,1,0,0]
q = []
q.append((start_x,start_y))
result = False
while q:
x, y = q.pop(0)
for l in range(4):
mx = x+dx[l]
my = y+dy[l]
if 0 <= mx < 16 and 0 <= my < 16:
# print(arr[mx][my])
# print(mx, my)
if arr[mx][my] == 0 and v[mx][my] == False:
q.append((mx,my))
v[mx][my] = True
# print(q)
elif arr[mx][my] == 3:
result = True
break
if result == True:
print(f'#{i+1}',"1")
else:
print(f'#{i+1}',"0")
코드 최근에 BFS, DFS 공부해서 코드 흐름을 외워버렸다….입력받는 미로 내용을 arr에 저장하고
v를 통해서 이미 방문했는지 확인합니다.
시작 2, 종료 3입니다.
1. 2 위치를 찾아줍니다. x, y를 한 번씩 돌려주면 찾아지겠죠?
2. start_x, start_y를 통해서 시작할 위치 x, y를 이용합니다.
3. q에 (x, y)를 추가 해놓는데 잘 보면 q.append((x, y)) 괄호 2개를 사용했죠?? 이 부분은 저도 공부하면서 배운 건데 이 방법을 통해서 x, y = q.pop(0)을 통해서 (x, y)가 한 번에 나오는 거 같았어요.
4. while을 통해서 q가 더 이상 없을 때까지 반복합니다.
5. x, y = q.pop(0)가장 앞에 있는 배열 빼 옵니다.
6. for 4번 반복을 통해서 dx, dy를 통해서 상, 하, 좌, 우의값을 값을 조건에 맞으면 q.append 해줍니다.
7. 조건 : arr[mx][my] == 0 and v[mx][my] == False 이동 경로가 0이고, 방문하지 않았다면 조건에 맞아요
8. q.apppend((mx,my))를 통해 위치를 q에 넣어주고, 방문할 테니까 v[mx][my] = True로 변경합니다.
이 방식으로 0인 위치를 모두 방문합니다.
만약 3을 발견했다면 result =True를 통해서 찾았다고 변경해 주고 더이상 볼 필요가 없으므로 탈출합니다.
8-1 q가 비었다는 건, 0이면서, 방문 안 한 곳이 더 이상 없다는 뜻이기 때문에 끝이 난 거예요!
9. 출력 부분에서 result 조건에 맞게 출력해 주변 끝! 끝!