[이것이 코딩테스트다] 8일차 - 미로탈출 | 백준 특정 거리의 도시 찾기

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.

Chapter 5 DFS/BFS

오늘 풀이한 문제는 다음 두가지이다

[이코테 152P] 미로탈출

문제설명 N by M 크기의 직사각형 형태의 미로에 갇혀있다. 미로에는 괴물이 있어 이를 피해서 탈출해야 한다. 유저의 초기 위치는 (1, 1)이고 미로의 출구는 (N, M) 위치에 존재하며 한 번에 한 칸 씩 이동이 가능하다. 이 때 괴물이 있는 부분은 0, 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이 때 유저가 미로를 탈출하기 위해 움직여야 할 최소 칸의 개수를 구해라. 단, 칸을 셀 때 시작, 마지막 칸도 포함시켜야 한다. 입력조건 첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다. 출력조건 첫째 줄에 최소 이동 칸의 개수를 출력한다

- (해명 time) 어제 처음 dfs, bfs를 코드로 구현해봐서 머리로는 bfs로 칸을 옮겨가며 하면 되겠다 생각은 났지만 코드로 구현을 못했다,,, 

- 어제 dfs 예제를 풀어봐서 조금의 아이디어를 떠올릴수 있어서 bfs도 일단 연습문제까지는 풀이를 학습하고 기출을 도움없이 풀어보기로 했다 

 

느낀점

- dx, dy를 이용해서 위치 조정하는걸 자꾸 까먹는다 계속 연습을 통해 익숙해져야겠다

- 위치를 조정할때 cnt 변수를 사용하지 않고 칸의 값을 올리면서 마지막 출구 칸의 값을 return 하였다 (감탄만 나옴,, 진짜 똑똑하신,,,,,,,,,,,,,,,,,,,,,)

- 어제 dfs 연습문제랑 이거랑 반복해서 풀면서 감을 익혀야겠다

from collections import deque 

graph = [[1,0,1,0,1,0],
        [1,1,1,1,1,1],
        [0,0,0,0,0,1],
        [1,1,1,1,1,1],
        [1,1,1,1,1,1]]

n,m = 5, 6

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
                
            if graph[nx][ny] == 0:
                continue
            
            if graph[nx][ny] == 1:
                queue.append((nx, ny))
                graph[nx][ny] = graph[x][y] +1
                if nx == n-1 and  ny == m-1:
                    return graph[n-1][m-1]

print (bfs(0,0))

 

[백준 18352] 특정 거리의 도시 찾기

- BFS로 구현 가능한 문제 - 처음 풀이할 때는 큐에 city num만 추가하려 했지만 거리를 +1 하기 쉽지 않았다 - 큐에 city num과 cnt를 같이 넣고 해당 도시에 들르면 cnt 도 같이 pop하도록 해서 해결했다 (검색 찬스) - bfs에 조금 가까워진 느낌이 든다

from collections import deque

def bfs (connect, x, visited):
    k_city = [] ## 결과 값
    visited[x] = True 
    queue = deque()
    queue.append((x,0))  ## 시작 도시와 cnt 초기 값 입력
    while queue:
        city, cnt = queue.popleft()  
        if cnt == k:
            k_city.append(city)
            
        for node in connect[city]:  ## 도시가 들리는 다음 도시들 
            if visited[node] == False: 
                queue.append((node, cnt+1)) 
                visited[node] = True
    if k_city == []: ## 조거에 만족하는 도시가 없을때 
        return -1
    
    return k_city
    
n,m,k,x = 4,4,2,1 ## 도시 개수, 도로 개수, 최단 거리, 출발 도시
info = [[1, 2],
       [1,3],
       [2,3],
       [2,4]]

connect = [[] for _ in range(m+1)]  ## 도시와 연결된 다음 도시들 (index맞추기 위해 +1)
for i in info:
    connect[i[0]].append(i[1])  ## [[], [2, 3], [3, 4], [], []]

## 도시 방문 여부 
visited = [False for _ in range (n+1)]
bfs (connect, x, visited)

 

연습문제 풀이는 깃허브에도 업로드 되어있습니다 

GitHub - gymin97/algorithm_study: Solve the algorithm problems (python3)