A :stack은 별도의 라이브러리를 이용할 필요 없이 list에 append()와 pop() 함수를 이용해 구현한다. line 7과 10에서는 직전에 append된 7과 4가 출력되는 last in first out(first in last out) 특징을 확인할 수 있다.
[5-2] Q : 큐를 구현해라.
A :파이썬에서 큐는 collection 모듈의 deque 자료구조를 사용한다. Deque(Double Ended Queue)는 양 끝에서 삽입과 삭제를 할 수 있어야 하므로 양방향 연결리스트(dobuly linked list)로 구현되어 있다. 오른쪽에 삽입할 때는 append(), 왼쪽에 삽입할 때에는 appendleft(), 중간에 삽입할 때에는 insert(index,num)을 사용하고, 오른쪽에서 빼낼때는 pop(), 왼쪽에서 빼낼때는 popleft()를 사용한다. Deque는 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이다. line 10과 line 13에서 가장 먼저 입력했단 5와 2가 차례로 빠져나오는 것을 확인할 수 있다. 이를 통해 First In First Out(Last In Last Out) 특성을 확인할 수 있다. line 10을 보고 popright()도 되는지 테스트해봤는데, 해당 함수 자체가 존재하지 않는다. 그리고 line 16, 17을 합쳐 한 번에 print(queue.reverse())를 했는데, 그건 None이 출력된다. line 15에서 deque 자료형을 print하면 deque([3,7,1,4])처럼 출력되는데, 이를 list로 바꾸고 싶으면 list(queue)를 해주면 된다.
[5-3] Q : 팩토리얼 함수를 재귀함수로 구현해라.
A :
[5-4] Q : 노드가 3개인 그래프를 인접행렬 방식으로 구현해라
A :인접행렬 방식에서는 연결되어있지 않은 노드끼리는 무한의 비용(INF)이라고 작성한다. 인접행렬 방식에서는 각 노드들 간의 모든 관계를 표현해 준다.
[5-5] Q : 노드가 3개인 그래프를 인접리스트 방식으로 구현해라.
A :노드가 3개이므로 우선 행이 3개인 2차원 list를 만든다. Line 3,4는 0번 노드에 연결된 노드와 그 거리를 입력해준다. 각 노드와의 연결정보는 튜플 형태로 입력된다. 노드 0번은 1번 노드와는 거리가 7이고, 2번 노드와는 거리가 5이다.
인접행렬 방식과 인접리스트 방식을 비교해 보면, 인접리스트 방식은 연결된 정보만을 저장하기 때문에 메모리 측면에서는 효율적이다. 하지만 이런 속성 때문에 인접리스트 방식은 특정 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다. 연결된 데이터를 하나하나 확인해야 하기 때문이다. 노드 1과 7이 연결되어 있는지 보려면, 인접행렬 방식에서는 graph[1][7]만 확인하면 되지만, 인접리스트 방식에서는 노드1에 대한 인접리스트를 앞에서부터 차례로 확인해야 한다.
[5-6] Q : DFS를 구현해라.
A :
위 그래프를 line 8에 2차원 리스트로 표현한다. 노드의 번호는 1~8까지 있으므로 graph[0]은 비워두고 사용하지 않는다. graph[1]에서 1번 노드는 2,3,8번 노드와 연결되어 있다. 그리고 line 20에 방문한 노드인지 여부를 체크하기 위해 False를 9칸 만들어준다. 역시 마찬가지로 index 0은 사용하지 않는다.
DFS 함수에서 line 2에서는 지금 위치한 노드(v번 노드)를 방문처리 한다. 그리고 지금 방문했으므로 line 3에서 출력한다. line 4에서 graph[v]에는 v번 노드와 연결된 노드들이 들어있을 것이다. 그 노드들 중 아직 방문하지 않은 노드들이 있다면 DFS를 재귀 호출해서 방문처리를 하고, 더 깊이 들어간다. 위 그림에선 1->2->7->6 순으로 깊게 들어가는데, 6번 노드에서는 연결된 노드들 중(line 15, 7번노드) 방문하지 않은 노드들이 없기에 line 4~6에서 DFS를 호출하지 않게 된다. 그럼 다시 v=7일때로 올라가고, line 4의 다음 i인 8번 노드에 대해 DFS 함수가 호출된다. 이런 식으로 깊이 우선 탐색(DFS)가 이루어진다. 일반적으로 인접한 노드들이 여러개면 번호가 작은 노드를 우선적으로 방문한다고 했는데, 이는 graph를 정의할 때 숫자가 작은 노드들부터 먼저 list에 넣어줬기에 line 4에서 차례로 호출된다. 마지막에는 line 4,5에 해당하는 i가 존재하지 않기 때문에 DFS가 더이상 호출되지 않게 되고, 함수가 종료된다.
DFS는 스택 자료구조에 기초해 구현되며, 데이터의 수가 N개인 경우 O(N)의 시간이 소요된다.
[5-7] Q : BFS를 구현해라.
A :BFS를 구현하기 위해 deque 모듈을 불러온다. DFS에서와 달리, BFS는 재귀적으로 BFS 함수를 호출하지 않는다. 때문에 큐도 line 4에서 함수가 시작할 때 한 번만 만든다. line 6에서 큐가 빌 때까지 계속 새 노드를 추가하고(line 11), 방문처리를 한다.
[5-8] Q : NxM 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려있는 부분끼리 붙어있는 경우 서로 연결된 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구해라. 첫째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. 두번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다.
A :DFS로 구현했다. DFS 함수에 좌표를 넣었을 때 주어진 범위를 벗어난다면 False를 리턴한다. 그리고 해당 좌표가 1로 표시되어 있어도 False가 리턴된다(line 18). Line 23에서 각 좌표를 돌아가며 DFS를 부르는데, DFS의 리턴값이 True면(line 10,16) result를 증가시킨다. Line 10에서 DFS에서 입력된 좌표값이 0이면 해당 칸을 1로 마킹하고(line 11), 상하좌우에 위치한 칸에 대해 DFS를 실행한다. 그리고 True를 리턴한다(line 16). Line 12~15에서 각 칸에 대해 DFS를 재귀적으로 호출하는데, 이 이동한 칸들에 대해서도 상하좌우 칸들에 대해 다시 line 12~15가 실행되어 DFS가 재귀적으로 호출된다. 이렇게 이동하다가 만약 대입된 칸이 1이거나 범위를 벗어나게 된다면 False를 리턴한다. 그리고 0으로 칠해졌던 칸들은 모두 line 11에 의해 1으로 칠해진다. 결국 line 23은 모든 칸들에 대해 판별을 하지만, 0인 칸이 하나만 line 23에 들어간다면, 그 칸과 연결된 0인 칸들은 모두 1로 바뀐다. 그리고 result는 결국 연결된 한 블럭에 대해 1만 증가하게 된다.
[5-9] Q : NxM 크기의 미로가 있다. 처음 위치는 (1,1)이고, 출구는 (N,M)에 위치해 있다. 한 번에 한 칸씩 이동할 수 있으며, 1인 칸은 이동할 수 있고, 0인 칸은 이동할 수 없다. 이 때, 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구해라. 첫째 줄에 두 정수 N,M이 주어진다. 다음 N개의 줄에는 각각 M개의 정수가 공백 없이 주어진다. 시작 칸과 마지막 칸은 항상 1이다.
A : 이 문제는 BFS를 사용하기 적합하다. BFS는 시작지점에서 가까운 노드부터 차례대로 모든 노드들을 탐색하기 때문이다. 따라서 시작점부터 BFS를 시작해 모든 노드의 거리정보를 넣으면 된다. 이전 노드까지의 거리에 1을 더한 값을 리스트로 넣는다. 이 문제에서 주어진 지도의 세로 길이가 N, 가로 길이가 M이다. 그런데 line 23, 26, 30에서 보듯이 이 코드에서는 좌표를 map_[x][y]꼴로 쓰고 있다. 이는 평소에 생각하는 (x,y) 좌표계와 반대 좌표다. Line 12에서는 BFS를 처음 실행시킬 때 큐를 만들어준다. 어차피 BFS는 재귀적으로 호출이 일어나는 것이 아니기 때문에 처음에 한 번만 만들어주면 된다. Line 20~24에서는 이동할 수 없는 칸에는 그냥 아무것도 해주지 않고 넘어간다. line 26~28에선 주변 칸이 1인 경우에만 거리를 업데이트 해주고 큐에 넣어준다. 오른쪽에서 map_을 print한 결과를 보면 아래 두 행에서 최단 경로가 아닌 곳에서도 길이가 증가한 것을 볼 수 있는데, 시작점에서 가장 거리가 먼 왼쪽 아래는 15가 적혀 있음을 볼 수 있다. 15에서 오른쪽으로 가며 16,17,...으로 증가하지 않은 이유는, BFS의 특성상 동일한 level에 있는 노드들은 동시에 업데이트 되고, 때문에 15라는 거리가 업데이트 되기 전에 미리 거리가 14인 두 노드가 업데이트되기 때문이다. 그리고 역으로 출구 왼쪽에서 11인데 출구의 거리가 12로 업데이트 되지 않는 것은, line 26에서 주변 노드가 1인 경우(거리가 아직 밝혀지지 않은 경우)만 업데이트를 진행하도록 해두었기 때문이다. BFS에서는 동일 레벨에 있는 노드들은 동시에 업데이트가 되기 때문에, 최단 경로의 숫자가 각 노드들에 업데이트 된다.
