Day 7 코딩테스트_탐색

DFS

깊이 중심, Stack 으로 처리

지도 코드화

• 인접 행렬 방식 : 파이썬 코드화 (list)
• 인접 리스트 방식 : 파이썬 코드화 (list/dict)

인접 리스트 방식 표현 (list vs dict -> list 선택)

graph_list = [
    [], # 가상의 0번 도시 가정,
    [2,3,8], # 1번 도시의 연결된 도시(직접)
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

틀

• 입력 : 지도, 시작점
• 기능 : DFS 방식으로 주어진 지도 탐색/방문
• 출력 : 방문 기록 제출

def dfs_m1(graph, start):

1. 초기 변수 세팅
   1.1 방문할 곳 리스트 (To do list)
   need_visit = list()
   1.2 방문한 곳 리스트 (Done list)
   visited = list()

2. 출발지 방문할 곳에 추가
   need_visit.append(start)

3. To do list 비울 때 까지 롤링

while need_visit :
	node = need_visit.pop() #stack
    if node not in visited : #신규 방문지 체크
    	visited.append(node) #신규 방문지일 경우 Done list에 추가, 
        need_visit.extend(graph[node]) #연결된 도시들 To do list에 추가

위 코드의 문제점 : 동일한 연결에서 도시 번호가 큰 순서대로 방문하게 됨.

		visited.append( node )
            #### 순서 지정 : 같은 조건일 때 작은 번호 먼저.
            #    역방향 : .reverse(), reversed(), [::-1], sort/sorted
            temp = graph[node]
            temp_reverse = list(reversed(temp))
            need_visit.extend( temp_reverse )
            # need_visit.extend( graph[node][::-1])

4. 출력
   return visited
   -> [1, 2, 7, 6, 8, 3, 4, 5]

BFS

너비 중심, Queue 로 처리
스케일링 큐 방식?

*DFS과 동일하게 지도 코드화 (graph_list)

틀

1. 초기 변수 세팅
   1.1 방문할 곳 리스트 (To do list)
   need_visit = list()
   1.2 방문한 곳 리스트 (Done list)
   visited = list()

2. 출발지 방문할 곳에 추가
   need_visit.append(start)

(까지 DFS와 동일)

3. To do list 비울 때 까지 롤링
   신규인지 체크하고 신규일 경우 새로운 할 일 추가

while need_visit :
	node = need_visit.pop(0) #queue, pop(0)
    if node not in visited : #신규 방문지 체크
    	visited.append(node) #신규 방문지일 경우 Done list에 추가, 
        need_visit.extend(graph[node]) #연결된 도시들 To do list에 추가

4. 출력
   return visited
   -> [1, 2, 3, 8, 7, 4, 5, 6]

DFS vs BFS

• DFS : 해야할 일에 대한 관리 = Stack (할 일은 맨 뒤에 추가) (선택은 맨 뒤에서 뽑아서)
• BFS : 해야할 일에 대한 관리 = Queue (할 일은 맨 뒤에 추가) (선택은 맨 앞에서 뽑아서)
  ==> 모든 곳들은 다 방문을 할 수 있음 but 방문하는 스타일이 달라진다
• DFS : 꼬리에 꼬리를 물면서 진행 > 깊이 중심 (출발점에 일단 멀리)
• BFS : 맨 앞에서 부터 하나씩 순차적인 해결 > 시작점 중심 방사형/너비중심

BFS > Queue > deque 패키지

Python Queue 의 속도 문제를 해결하기 위해 collection 패키지의 deque 모듈 사용
from collections import deque
deque([ , , , ])

list와 유사 : .append(), .pop() 가능
❗ .pop(0) - 맨 앞에서 원소 빼기 불가능! -> .popleft() 사용

01. 탐색_BFS_최단거리

다익스트라알고리즘

Q.
어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

[입력]
첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.
[출력]
X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.
이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

[입출력 예시]
입력 :
4 4 2 1
1 2
1 3
2 3
2 4
출력 :
4

---

A.
#연결에 방향성이 있으며 거리 정보는 모두 1로 동일함.

1. 입력 처리

    # 할 일 : 방문할 도시 - 기존 bfs와 동일 : deque
    q = deque()
    # 한 일 : 거리 정보 기록, 방문한 도시 -> 거리로 수정
    #       : 초기값 세팅 X, 거리 너무 멈 => inf
    INF = float("inf")
    distance = [INF] * (n+1) # 0번 가상 도시 포함
    # [inf(0), inf(1),inf(2),inf(3),inf(4)]

2. 초기화

2-1) 할 일에 대한 초기화

    q.append(start)

2-2) 출발점에 대한 거리정보 초기화! #다른 점

    distance[start] = 0

3. 큰 틀

    while q:
        # 할 일 꺼내기 - 앞에서(bfs, popleft())
        now = q.popleft()
        # 지금 여기서 1칸으로 연결된 도시들을 체크
        for next_node in graph[now]:
            # 신규 방문지인지 체크
            if distance[next_node] == INF:
                # 거리 갱신! 도장!
                distance[next_node] = distance[now] + 1
                # 새롭게 할 일 부여 받기 : next_node에 가서..
                q.append(next_node)
    return distance

02. 탐색_BFS_미로탈출

DFS 는 back 하기 때문에 순차적으로 숫자 기록 못함 -> BFS 사용

Q.
N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

[입력]
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
[출력]
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

[입출력 예]
입력 :
4 6
101111
101010
101011
111011
출력 :
15
입력 :
2 25
1011101110111011101110111
1110111011101110111011101
출력 :
38

---

A.

1. 입력처리

n, m = map(int, input("가로세로 크기를 입력하세요").split(" "))

graph = []
for i in range(n) :
	t = input("n,m에 대한 {0}번째 가로줄".format(i+1)) #1,2,3,..n번째 줄 정보 받기
    t = list(map(int, [i for i in t])) #int로 변환하여 list화 하기
    graph.append(t)

2. 한 일과 할 일

• ToDo : [(x,y)] 좌표 값으로 표현해야함

from collections import deque
q = deque() #To Do #[(x_pos, y_pos), ...]
x_pos = start[0] #입력값으로 준 시작칸 좌표
y_pos = start[1]

• Done : 거리로 graph에 직접 기록

• 출발점

q.append([(x_pos, y_pos)])

3. 큰 틀

방문할 곳 pop(0)
graph 벗어나면 pass, 값이 0이면 pass

1. LRUD 이동

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

2. 방문할 곳 선택, 롤링

while q :
	now_x, now_y = q.popleft() #bfs니까 맨 앞 선택
    for i in range(4) : #LRUD #갈 수 있는 곳 순회
    	next_x = now_x + dx[i]
        next_y = now_y + dy[i]
        # 1. in/out 체크 (지도 내부에 위치하는가?)
        if 0 <= next_x < n and 0 <= next_y < m :
        	# 2. 내가 온 곳이 처음인지 + 이동 가능한 지(0칸 X)
            if gragh[next_x][next_y] == 1 : #지도에서 값 뽑아서 1인지 확인
            	gragh[next_x][next_y] = graph[now_x][now_y]+1 #거리 갱신! #도장찍기
                q.append((next_x, next_y))
    return[n-1][m-1] #마지막 칸의 거리 값 출력

---

03. 탐색_얼음얼리기

Q.

A.
탐색의 순서가 무관하므로 DFS / BFS 둘 다 가능한 유형
모든 점을 시작점으로 하고 카드 뒤집기(0>1)... 큰 틀에서 counting

코드 틀 짜보면 :

for i in 가로줄 :
	for j in 세로줄 :
    	-> (i,j)으로 모든 점 출발점으로 롤링
        if (i,j) 시작 가능 : #0인 경우
        	탐색
            #1로 도장 찍고
            #할 일 : LRUD로 이동해 in/out 체크, 0/1 체크 
            # -> 둘 다 OK라면 이동한 점에 도장 찍고(1), 할 일 부여받기(LRUD 추가)
			# --- 계속 할 일 롤링(다 할 때까지)
            탐색 종료 시 counting +1

• 입력 : 출발점 좌표 (row,col)
• 기능 : 출발점에서 이동이 가능하다면 모두 다 이동하고 체크 BFS/DFS
• 출력 : 출발점에서 시작할 수 있고, 방문을 하면 1 / 시작할 수 없다면 0

graph_45 = [
  	   [0,0,1,1,0],
  	   [0,0,0,1,1],
 	   [1,1,1,1,1],
 	   [0,0,0,0,0]
	]
    

#함수 생성
def bfs_ice(row_init, col_init) :
	if graph[row_init][col_init] == 0 : #시작점에서 시작할 수 있는지 체크
    	q = deque([[row_init, col_init]]) #[[]]주의 #할 일 초기 세팅
        graph[row_init][col_init] = 1 #도장 찍기
        
        while True : #무한루프
        	if not q : #q 원소가 없을 때 (할 일 비었을 때) - 탈출 조건
            	return 1
            row, col = q.popleft()
            for dx, dy in [[0,-1],[0,1],[-1,0],[1,0]] : #LRUD ListUp
            	if 0 <= row + dx < n and 0 <= col + dy < m : #경계조건 체크
                	if graph[row+dx][col+dy] == 0 : #얼음조건 체크
                    	graph[row+dx][col+dy] == 1 #도장찍기
                        q.append([row+dx, col+dy]) #할 일 추가
    else :
    	return 0
        
        
n,m = 4, 5     
cnt = 0
for row in range(n) :
	for col in range(m) :
		cnt += bfs_ice(row, col)

❓ DFS로 한다면 (재귀함수)

def dfs_recursive(row,col) :
	if row <= -1 or row >= n or col <= -1 or col >= m : #경계조건 체크
    	return False
    if graph[row][col] == 0: #얼음조건 체크
    	graph[row][col] = 1 #도장(0>1)
        #LRUD, 할 수 있는 데까지 쭉~ 실행됨. stack처럼 동작
        dfs_recursive(row,col-1) #L
        dfs_recursive(row,col+1) #R
        dfs_recursive(row-1,col) #U
        dfs_recursive(row+1,col) #D
        return True
    return False

머리가 아푸네요