파이썬 좌표 문제 입력 받는 방법(DFS, BFS) 퀵소트 코드

파이썬 알고리즘 공부를 시작한 지 벌써 일주일이 지났습니다. 

점차 2차원 리스트를 입력받는 부분도 익숙해지고, 함수 선언하는 부분을 자연스럽게 작성할 수 있게 됐습니다. 

 

이번 포스트에서는 파이썬 좌표 문제에서 2차원 map이 주어졌을 때 입력받는 방법과 DFS, BFS를 다루고,

마지막 부분엔 퀵 소트 코드를 소개합니다. 

 

파이썬 좌표 문제

python

C언어에서는 for문과 scanf()로 2차원 배열을 입력받는 것이 익숙했는데,

파이썬에서 2차원 리스트를 받으려면 조금 다른 발상이 필요합니다. 

[] 리스트로 먼저 초기화하고, append로 list안에 list를 채우는 방식으로 입력을 받을 수 있습니다. 

#2차원 리스트의 뱁 정보 입력 받기
#3 3
#001
#010
#101
graph =[]
for i in range(n):
    graph.append(list(map(int, input())))

 

인접 행렬 방식 예제 

인접행렬은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식입니다. 

INF로 연결이 되어 있지 않은 노드를 표시하고, 자기 자신은 0의 비용이라고 작성하면 됩니다. 

#인접 행렬 방식 예제
INF = 999999999 #무한의 비용 선언

#2차원 리스트를 이용해 인접 행렬 표현
graph=[
    [0,7,5],
    [7,0,INF],
    [5,INF,0]
]

print(graph)
#결과 [[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]

 

인접 리스트 방식 예제 

인접 리스트는 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장합니다. 

#인접 리스트 예제
#행이 3개인 2차원 리스트로 인접 리스트 표현
graph =[[] for _ in range(3)]

#노드0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1,7))
graph[0].append((2,5))

#노드1에 연결된 노드 정보 저장
graph[1].append((0,7))

#노드2에 연결된 노드 정보 저장
graph[2].append((0,5))

print(graph)
#[[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

 

DFS 예제

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다.

방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 

3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다. 

dfs graph

 

#DFS 예제
#DFS 메서드 정의
def dfs(graph, v, visited):
    #현재 노드를 방문 처리
    visited[v]=True
    print(v,end=' ')
    #현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

#각 노드가 연결된 정보를 리스트 자료형으로 표현
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

#각 노드가 방문된 정보를 리스트 자료형으로 표현
visited = [False]*9

#정의된 DFS 함수 호출
dfs(graph, 1, visited)
#출력: 1 2 7 6 8 3 4 5

 

BFS 예제

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 

 

#BFS 예제
#queue를 사용하기 위해서 deque를 collections에서 import합니다.
from collections import deque

#BFS 메서드 저의
def bfs(graph, start, visited):
    #큐 구현을 위해 deque 라이브러리 사용
    queue=deque([start])
    #현재 노드를 방문 처리
    visited[start]=True
    #큐가 빌 때까지 반복
    while queue:
        #큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v,end=' ')
        #해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True

#각 노드가 연결된 정보를 리스트 자료형으로 표현
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

#각 노드가 방문된 정보를 리스트 자료형으로 표현
visited= [False]*9

#정의된 BFS 함수 호출
bfs(graph, 1, visited)
#출력 1 2 3 8 7 4 5 6

 

음료수 얼려 먹기

DFS 문제 예제인데, Queue를 사용하여 BFS 방식으로 풀이했습니다. 

그리고 문제 풀 때 만든 실수는 for i range(n):을 쓰고 nx, ny 만들 때 for i in range(n)을 또 써버려서 오류가 발생했습니다. 

i를 k로 바꿔주니 괜찮아졌습니다. 

#my answer
from collections import deque
#n, m을 공백으로 구분하여 입력받기
n, m=map(int, input().split())

#2차원 리스트의 맵 정보 입력 받기 
graph=[]
for i in range(n):
    graph.append(list(map(int, input())))

visited=[[False]*m for _ in range(n)]
ans=0

for i in range(n):
    for j in range(m):
        if graph[i][j]== 0 and visited[i][j]==False:
            ans+=1
            visited[i][j]=True
            queue=deque()
            queue.append((i,j))
            while queue:
                v=queue.popleft()
                dx=[0,0,1,-1]
                dy=[1,-1,0,0]
                for k in range(4):
                    nx=v[0]+dx[k]
                    ny=v[1]+dy[k]
                    if nx>=0 and nx<n and ny>=0 and ny<m:
                        if visited[nx][ny]==False and graph[nx][ny]==0:
                            queue.append((nx,ny))
                            visited[nx][ny]=True

print(ans)
# 4 5
# 00110
# 00011
# 11111
# 00000
#출력 3

DFS 방식으로 푼 예제 

#book answer
#N,M을 공백으로 입력받기
n, m=map(int, input().split())

#2차원 리스트의 맵 정보 입력 받기
graph =[]
for i in range(n):
    graph.append(list(map(int,input())))

#DFS로 특정한 노드를 방문한 뒤에 연결된 모드 노드들도 방문
def dfs(x,y):
    #주어진 범위를 벗어나는 경우에는 즉시 종료
    if x<=-1 or x>=n or y<=-1 or y>=m:
        return False
    #현재 노드를 아직 방문하지 않았다면
    if graph[x][y]==0:
        #해당 노드 방문 처리
        graph[x][y]=1
        #상, 하, 좌, 우의 위치도 모두 재귀적으로 호출
        dfs(x-1, y)
        dfs(x,y-1)
        dfs(x+1, y)
        dfs(x,y+1)
        return True
    return False

#모든 노드(위치)에 대하여 음료수 채우기
result=0
for i in range(n):
    for j in range(m):
        #현재 위치에서 dfs 수행
        if dfs(i,j)==True:
            result+=1
        
print(result) #정답 출력

미로탈출 BFS 예제

#미로탈출
from collections import deque

INF=999999999
n, m=map(int,input().split())
graph = []
for i in range(n):
    graph.append(list(map(int,input())))

visited = [[INF]*m for _ in range(n)]

def bfs(graph, start_x, start_y, visited):
    queue = deque()
    queue.append((start_x, start_y))
    visited[start_x][start_y]=1
    while queue:
        v= queue.popleft()
        dx=[0,0,1,-1]
        dy=[1,-1,0,0]
        for k in range(4):
            nx=v[0]+dx[k]
            ny=v[1]+dy[k]
            if nx<=-1 or nx>=n or ny<=-1 or ny>=m:
                continue
            else:
                if graph[nx][ny]==1:
                    if visited[nx][ny] > visited[v[0]][v[1]] +1:
                        visited[nx][ny]=visited[v[0]][v[1]]+1
                        queue.append((nx, ny))

bfs(graph, 0, 0, visited)
print(visited[n-1][m-1])

퀵 소트 예제

array = [1,8,4,7,2,3,6,0,5,9]

def quick_sort(array, start,end):
    if start >=end:
        return
    pivot = start
    left=start+1
    right=end
    while left <= right:
        #피벗보다 큰 데이터를 찾을 때까지 반복
        while left <=end and array[left] <= array[pivot]:
            left+=1
        #피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[right]>=array[pivot]:
            right-=1

        if left >right:  #엊갈렸다면 작은 right -=1 데이터와 피벗을 교체
            array[right], array[pivot]=array[pivot], array[right]
        else: #엊갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right]= array[right], array[left]

    #분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)

quick_sort(array, 0,len(array)-1)
print(array)
#결과 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

퀵 소트 파이썬 방식 예제 

array = [1,8,4,7,2,3,6,0,5,9]

def quick_sort_py(array):
    #리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <=1:
        return array

    pivot = array[0] #피벗은 첫 번째 원소
    tail = array[1:] #피벗을 제외한 리스트

    left_side =[x for x in tail if x <=pivot] #분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot] #분할된 오른쪽 부분

    #분할 이후 왼쪽 부분과 오른쪽 부분에서 각 정렬을 수행하고, 전체 리스트를 반환
    return quick_sort_py(left_side)+[pivot]+quick_sort_py(right_side)

print(quick_sort_py(array))
#결과 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]