미로찾기 알고리즘
미로찾기 예제)
아래 그림과 같은 미로가 있다. 16*16 행렬의 형태로 만들어진 미로에서 흰색 바탕은 길, 노란색 바탕은 벽을 나타낸다.
가장 좌상단에 있는 칸을 (0, 0)의 기준으로 하여, 가로방향을 x 방향, 세로방향을 y 방향이라고 할 때, 미로의 시작점은 (1, 1)이고 도착점은 (13, 13)이다.
주어진 미로의 출발점으로부터 도착지점까지 갈 수 있는 길이 있는지 판단하는 프로그램을 작성하라.
아래 예시는 도착 가능한 경우
[입력]
각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.
총 10개의 테스트케이스가 주어진다.
테스트 케이스에서 1은 벽을 나타내며 0은 길, 2는 출발점, 3은 도착점을 나타낸다.
[출력]
#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 도달 가능 여부를 1 또는 0으로 표시한다 (1 - 가능함, 0 - 가능하지 않음).
DFS
- Stack 사용
# 순서 상관 없어..
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]
# 2에서 3까지 갈 수 있으면 1을 return 하고 아니면 0
def dfs(curR, curC):
visited = [[False]*N for _ in range(N)]
ST = []
# 1. 스택에 시작점을 push, 방문표시
ST.append((curR, curC))
visited[curR][curC] = True
# 2. 스택에 데이터가 있는 동안 반복
while ST:
curR, curC = ST.pop()
# cur point와 연결된 모든 point에 대하여
for d in range(4):
newR = curR + dr[d]
newC = curC + dc[d]
# new가 이동이 가능하면
# 방문 안했으면
# 0 또는 3 일때 방문해야 하므로 miro[newR][newC] != 1 이 조건 사용
if 0 <= newR < N and 0 <= newC < N and miro[newR][newC] != 1 and not visited[newR][newC]:
# 3에 도달하면 return 1
if miro[newR][newC] == 3:
return 1
# 연결된 부분은 스택에 넣어..
ST.append((newR, newC))
visited[newR][newC] = True
return 0
for test_case in range(1, 11):
TC = int(input())
N = 16
miro = [list(map(int, input())) for _ in range(N)]
ST = []
# 시작위치
for row in range(N):
if miro[row].count(2):
curC = miro[row].index(2)
curR = row
break
print(f'#{test_case} {dfs(curR, curC)}')
BFS
- Queue 사용
def bfs(i, j):
visited = [[0]*16 for _ in range(16)]
Q = []
# 시작점 큐에 넣고 방문표시
Q.append((i, j))
visited[i][j] = 1
while Q:
i, j = Q.pop(0)
# 3에 도달하면 1을 리턴한다
if maze[i][j] == 3:
return 1
for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
ni, nj = i + di, j + dj
# 가장 바깥쪽 벽이 1로 둘러싸여 있기 때문에 0 <= __ < N 조건 안해도돼
# 벽이 아니고 방문표시가 되어있지 않을 때 이동한다.
if 0 <= ni < 16 and 0 <= nj < 16 and maze[ni][nj] != 1 and visited[ni][nj] == 0:
Q.append((ni, nj))
visited[ni][nj] = 1
# 경로가 존재하지 않으면 0을 리턴한다.
return 0
for test_case in range(1, 11):
TC = int(input())
maze = [list(map(int, input())) for _ in range(16)]
# print(maze)
# 시작위치 찾기
sti = -1
stj = -1
for i in range(16):
for j in range(16):
if maze[i][j] == 2:
sti, stj = i, j
if sti != -1:
break
# print(sti, stj)
print(f'#{TC} {bfs(sti, stj)}')
최단 경로를 찾는 문제
BFS 로 탐색할 때는 가장 먼저 찾아진 경로가 곧 최단 경로가 된다. 방금 알았네 ㅎ
부모 노드부터 등고선과 같이 탐색하기 때문에 가장 짧을 수 밖에 없는 것 같다... 뭐지..
반대로 이를 DFS로 구현할 때는 모든 경로를 다 검사하면서 최솟값을 찾아내야 한다.
" BFS, DFS 두가지 방법으로 아래 예제 풀어봤다!! "
최단경로 예제)
NxN 크기의 미로에서 출발지 목적지가 주어진다.
이때 최소 몇 개의 칸을 지나면 출발지에서 도착지에 다다를 수 있는지 알아내는 프로그램을 작성하시오.
경로가 있는 경우 출발에서 도착까지 가는데 지나야 하는 최소한의 칸 수를, 경로가 없는 경우 0을 출력한다.
다음은 5x5 미로의 예이다. 1은 벽, 0은 통로를 나타내며 미로 밖으로 벗어나서는 안된다.
13101
10101
10101
10101
10021
마지막 줄의 2에서 출발해서 0인 통로를 따라 이동하면 맨 윗줄의 3에 5개의 칸을 지나 도착할 수 있다.
[입력]
첫 줄에 테스트 케이스 개수 T가 주어진다. 1<=T<=50
다음 줄부터 테스트 케이스의 별로 미로의 크기 N과 N개의 줄에 걸쳐 미로의 통로와 벽에 대한 정보가 주어진다. 5<=N<=100
0은 통로, 1은 벽, 2는 출발, 3은 도착이다.
[출력]
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.
BFS
def bfs(i, j, N):
global minV
visited = [[0]*N for _ in range(N)]
Q = []
# 첫째 노드 방문하기
Q.append((i, j))
visited[i][j] = 1
while Q:
i, j = Q.pop(0)
# 노드에 방문해서 할일 -> visit(v)
# 이 문제에서는 현재 노드가 3번인지 확인 해야함
# 여기서 리턴한 값이 최단 경로가 된다.
if maze[i][j] == 3:
return visited[i][j]
for di, dj in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
ni, nj = i+di, j+dj
# 인덱스를 벗어나지 않고 벽(1)이 아니며 방문한 적이 없는 노드이면
if 0 <= ni < N and 0 <= nj < N and maze[ni][nj] != 1 and visited[ni][nj] == 0:
Q.append((ni, nj))
visited[ni][nj] = visited[i][j] + 1
return 0
T = int(input())
for test_case in range(1, T+1):
N = int(input())
maze = [list(map(int, input())) for _ in range(N)]
minV = 9999999
sti = -1
stj = -1
# 시작점 찾기
for i in range(N):
for j in range(N):
if maze[i][j] == 2:
sti = i
stj = j
break
if sti != -1:
break
# 시작점 끝점 제외해주기,
if bfs(sti, stj, N) == 0:
print(f'#{test_case} {bfs(sti, stj, N)}')
else:
print(f'#{test_case} {bfs(sti, stj, N)-2}')
DFS
'''
깊이 우선으로 구현할 경우에는 최단 거리를 구하기 위해서 모든 경로를 찾아야 한다.
-> 다 구하기 전까지는 최단이라는 사실이 보장이 안되는것 같네,,,뭐,, 당욘한거겟지
최단거리 찾기
-> 이전까지 지나온 칸수 + 1하면서 구해주기
'''
def dfs(i, j , s, N):
global minV
# 3에 도착하는 개수 = 경로의 개수
if maze[i][j] == 3:
# 도착하는 점을 포함하기 때문에 s+1
if minV > s + 1:
minV = s + 1
return minV
else:
visited[i][j] = 1
for di, dj in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
ni, nj = i + di, j + dj
# 인덱스를 벗어나지 않고 벽(1)이 아니며 방문한 적이 없는 노드이면
if 0 <= ni < N and 0 <= nj < N and maze[ni][nj] != 1 and visited[ni][nj] == 0:
dfs(ni, nj, s, N)
# 방문여부 다시 지워줘야해,,,다음에 다른 경로로 접근했을때 방문 가능하도록
visited[i][j] = 1
return 0
T = int(input())
for test_case in range(1, T+1):
N = int(input())
maze = [list(map(int, input())) for _ in range(N)]
minV = N*N
sti = -1
stj = -1
# 시작점 찾기
for i in range(N):
for j in range(N):
if maze[i][j] == 2:
sti = i
stj = j
break
if sti != -1:
break
visited = [[0]*N for _ in range(N)]
dfs(sti, stj, 0, N)
if minV == N*N:
numV = -1
print(minV)
새벽에 잠깐 깨서 화장실 다녀오다가 하늘 보고 바로 카메라 켜기.
너무 예뻐. 이거 찍으려고 문을 열었다가, 공기가 차가워 정신이 확 들어버려서 다시 잠들진 못했다.
요 몇일은 새벽에 자꾸 깼다. 그래서 오후엔 너무 힘들다.
오늘은 프로님과 면담도 했다!
면담 전에 마음 먹었던 것 보다 더 솔직하게 내 이야기를 하게 돼서 스스로 조금 놀라긴 했지만,
몸과 마음 건강히 취준 기간을 잘 보내고 있는것 같다? 라는 결론.
++++
..이라고 교육장에서 생각했는데 집에 와보니 아닌 것 같다.
왠지 모르게 울컥해서 눈물 그렁했는데 생각해보니 그럴시간 없음 ㅋㅋㅋㅋㅋ
그래도 오늘은 조금만 하고 자야지!
댓글