졍's 기술 블로그

미로 탐색

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 192 MB
알고리즘 분류 : 그래프 이론, 그래프 탐색, 너비 우선 탐색

문제

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

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

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입출력

Algorithm

BFS
1. 그래프 구현
2. BFS 돌면서 문제 조건에 따라 갈 수 없는 곳이 아니라면 큐에 모두 추가
3. 도착지점에 도착하면 이동 횟수 return

Code

from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(graph, sx, sy, ex, ey, visited):
    queue = deque()
    queue.append((sx, sy))

    while queue:
        x, y = queue.popleft()

        for dir in range(4):
            nx = x + dx[dir]
            ny = y + dy[dir]

            # 도착지에 도착하면 return
            if nx == ex and ny == ey:
                return visited[x][y] + 1
            
            # graph 밖으로 나가면 continue
            if nx < 0 or nx > N-1 or ny < 0 or ny > M-1:
                continue

            # 방문한 적 있으면 continue
            if visited[nx][ny]:
                continue

            # 0이면 continue
            if not graph[nx][ny]:
                continue

            # 방문 기록
            visited[nx][ny] = visited[x][y] + 1
            queue.append((nx, ny))

N, M = map(int, input().split())

graph = []
visited = [[0 for _ in range(M)] for _ in range(N)]
for _ in range(N):
    graph.append(list(map(int, input())))

print(bfs(graph, 0, 0, N-1, M-1, visited)+1)

메모리: 34168 KB
시간: 76 ms

깊이 우선 탐색(DFS, Depth First Search)

특정 Data를 탐색할 때 깊이가 깊은 것을 우선적으로 탐색하는 알고리즘으로 Stack 자료구조를 사용

사실 Stack을 사용하지 않아도 구현이 가능한데, 이는 컴퓨터가 구조적으로 항상 Stack의 원리를 사용하기 때문이다.

깊이 우선 탐색(DFS) Sequence

더보기

Step 1: 시작 Node를 Stack에 넣고 방문 처리

Step 2: Stack의 최상단 Node 확인

Step 3: 최상단 Node에 방문하지 않은 인접 Node가 있다면 그 Node를 Stack에 넣고 방문 처리

           ☞ 방문하지 않은 인접 Node가 없으면 Stack에서 최상단 Node 삭제

Step 4: Step 2로 이동

Code

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

#define MAX 7
int visited[7];
vector <int> a[8];

void dfs(int x){
    // 이미 방문한 적 있으면 return
    if(visited[x]) return;

    // 방문 처리
    visited[x] = true;
    cout << x << " ";

    // 인접 노드 방문
    for(int i=0;i<a[x].size();i++){
        int y = a[x][i];
        dfs(y);
    }
}

int main(void){
    a[1].push_back(2);
    a[1].push_back(3);

    a[2].push_back(1);
    a[2].push_back(3);
    a[2].push_back(4);
    a[2].push_back(5);

    a[3].push_back(1);
    a[3].push_back(2);
    a[3].push_back(6);
    a[3].push_back(7);

    a[4].push_back(2);
    a[4].push_back(5);

    a[5].push_back(2);
    a[5].push_back(4);

    a[6].push_back(3);
    a[6].push_back(7);

    a[7].push_back(3);
    a[7].push_back(6);

    dfs(1);
}

출력

1 2 3 6 7 4 5

너비 우선 탐색(BFS, Breadth First Search)

특정 Data를 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 알고리즘

최단 경로를 찾아준다는 점에서 최단 길이를 보장해야할 때 많이 사용되며, Queue를 이용한다.

e.g., 미로 찾기

너비 우선 탐색(BFS) Sequence

더보기

Step 1: 시작 Node를 큐에 삽입하고 방문 처리

Step 2: Queue에서 하나의 Node를 꺼냄

Step 3: 연결된 Node 중 방문하지 않은 Node를 방문하고 큐에 삽입

Step 4: Step 2로 이동

∴ BFS 수행 순서: 1 2 3 4 5 6 7

Code

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

#define MAX 7
int visited[7]; // 방문 유무를 표시할 배열
vector<int> a[8];

void bfs(int start){
    queue<int> q;

    // 시작 노드 큐에 추가
    q.push(start);
    visited[start] = true;

    // 큐가 빌 때까지 반복
    while(!q.empty()){
        int x = q.front(); q.pop();
        cout << x << " ";

        // 현재 큐에서 꺼낸 Node와 인접한 노드 모두 방문
        for(int i=0;i<a[x].size();i++){
            int y = a[x][i];
            // 방문한 적 없는 노드이면 큐에 추가 후 방문 처리
            if(!visited[y]){
                q.push(y);
                visited[y] = true;
            }
        }
    }
}

int main(void){
    a[1].push_back(2);
    a[1].push_back(3);

    a[2].push_back(1);
    a[2].push_back(3);
    a[2].push_back(4);
    a[2].push_back(5);

    a[3].push_back(1);
    a[3].push_back(2);
    a[3].push_back(6);
    a[3].push_back(7);

    a[4].push_back(2);
    a[4].push_back(5);

    a[5].push_back(2);
    a[5].push_back(4);

    a[6].push_back(3);
    a[6].push_back(7);

    a[7].push_back(3);
    a[7].push_back(6);

    bfs(1);

    return 0;
}

출력

1 2 3 4 5 6 7

큐(Queue)

먼저 들어온 Data가 먼저 처리되는 선입선출(First In First Out, FIFO), 후입후출(Last In Last Out, LILO) 자료구조

큐(Queue) Sequence

더보기

명령: 삽입(7) → 삽입(5) → 삽입(4) → 삭제( ) → 삽입(6) → 삭제( )

Code

#include <iostream>
#include <queue>
using namespace std;

int main(void){
    queue<int> q;
    q.push(7);
    q.push(5);
    q.push(4);
    q.pop();
    q.push(6);
    q.pop();
    while(!q.empty()){
        cout << q.front() << " ";
        q.pop();
    }
    return 0;
}

출력

4 6

스택(Stack)

가장 마지막에 들어온 Data가 가장 먼저 처리되는 후입선출(Last In First Out, LIFO), 선입후출(First In Last Out, FILO) 자료구조

Stack 동작 Sequnce

더보기

명령: 삽입 (7) → 삽입(5) → 삽입(4) → 삭제() → 삽입(6) → 삭제()

Code

#include <iostream>
#include <stack>
using namespace std;

int main(void){
    stack<int> s;
    s.push(7);
    s.push(5);
    s.push(4);
    s.pop();
    s.push(6);
    s.pop();
    while(!s.empty()){
        cout << s.top() << " ";
        s.pop();
    }
    return 0;
}

출력

5 7

1181 단어 정렬

https://www.acmicpc.net/problem/1181

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 20000+10

int N;
string tmp;
vector <string> vec;

void Input(){
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> tmp;
        vec.push_back(tmp);
    }
}

void Output(){
    tmp = "";
    for(int i=0;i<N;i++)
        if(tmp == vec[i]) continue;
        else{
            cout << vec[i] << "\n";
            tmp = vec[i];
        }
}

bool comp(string a, string b){
    if(a.length() == b.length()) return a < b;
    else return a.length() < b.length();
}

void Sort(){
    sort(vec.begin(), vec.end(), comp);
}

int main(void){
    Input();
    Sort();
    Output();
    return 0;
}

1431 시리얼 번호

https://www.acmicpc.net/problem/1431

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 1000+10

int N;
vector <string> vec;

void Input(){
    string tmp="";
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> tmp;
        vec.push_back(tmp);
    }
}

void Output(){
    for(int i=0;i<N;i++)
        cout << vec[i] << "\n";
}

int cal(string word){
    int sum=0;
    // 숫자만 뽑아내기
    for(int i=0;i<word.length();i++){
        if('0' <= word[i] && word[i] <= '9'){
            sum += word[i] - '0';
        }
    }
    return sum;
}

bool comp(string a, string b){
    int sum_a, sum_b = 0;
    // A와 B의 길이가 다르면 짧은 것이 먼저온다
    if(a.length() != b.length()) return a.length() < b.length();
    // 서로 길이가 같다면 A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저 온다. (숫자인 것만 더한다)
    else{
        sum_a = cal(a);
        sum_b = cal(b);
        if(sum_a != sum_b) return sum_a < sum_b;
        else{
            // 만약 1, 2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다 숫자가 알파벳보다 사전순으로 작다.
            return a < b;
        }
    }
}

void Solution(){
    sort(vec.begin(), vec.end(), comp);
}

int main(void){
    Input();
    Solution();
    Output();
}

10989 수 정렬하기 3

https://www.acmicpc.net/problem/10989

Code

#include <iostream>
using namespace std;

int N;
int tmp;
int count_arr[10000+10];

int main(void){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> tmp;
        count_arr[tmp]++;
    }

    for(int i=1;i<10001;i++){
        while(count_arr[i]){
            cout << i << "\n";
            count_arr[i]--;
        }
    }
    return 0;
}

계수 정렬(Counting Sort)

범위 조건이 있을 때에 한해서 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort)보다 더 빠르게 정렬해야하는 경우 사용될 수 있는 알고리즘으로 단순히 크기를 기준으로 세는 알고리즘

모든 데이터에 한 번씩만 접근하면 된다는 점에서 매우 효율적인 알고리즘이다.

계수 정렬(Counting Sort) Sequence

더보기

Code

#include <iostream>
using namespace std;
#define MAX 5

int arr[] = {1, 3, 2, 4, 3, 2, 5, 3, 1, 2, 3, 4, 4, 3, 5, 1, 2, 3, 5, 2, 3, 1, 4, 3, 5, 1, 2, 1, 1, 1};
int count_arr[MAX+1] = {0,};

int main(void){
    for(int i=0;i<sizeof(arr)/4;i++){
        count_arr[arr[i]]++;
    }

    for(int i=0;i<MAX+1;i++){
    	if(count_arr[i]== 0) continue;
        for(int j=1;j<=count_arr[i];j++){
            cout << i << " ";
        }
    }
    return 0;
}

출력

1 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 5 5 5 5

시간 복잡도

모든 원소를 한 번씩만 확인하기 때문에 O(N)

힙 정렬(Heap Sort)

병합 정렬(Heap Sort)이나 퀵 정렬(Quick Sort)만큼 빠른 정렬 알고리즘으로 힙 트리 구조(Heap Tree Structure)를 사용하는 정렬 방법

추가적인 배열이 필요하지 않다는 점에서 메모리 측면에서 병합 정렬(Merge Sort)에 비해 효율적이며 항상 O(N*logN)을 보장한다.

이론적으로는 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort)보다 더 우위에 있다고 할 수는 있으나, 단순히 속도만 가지고 비교해보면 퀵 정렬(Quick Sort)이 평균적으로 더 빠르기 때문에 힙 정렬(Heap Sort)이 일반적으로 많이 사용되지는 않는다.

트리(Tree)

가지를 뻗어나가는 것 처럼 Data가 서로 연결되어 있는 자료구조

이진 트리(Binary Tree)

컴퓨터 안에서 Data를 표현할 때 데이터를 각 Node에 담은 뒤 Node를 두 개씩 이어붙이는 구조

Root: Tree의 최상단 Node

Leaf: Tree의 최하단 Node

완전 이진 트리(Complete Binary Tree)

Data가 Root Node부터 시작해서 자식 Node가 왼쪽 자식 Node, 오른쪽 자식 Node로 차근차근 뻗어나가는 구조의 이진 트리(Binary Tree)

힙(Heap)

최솟값이나 쵯댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리

최대 힙(Max Heap): 부모 노드가 자식 노드보다 큰 힙

-> 힙 정렬을 하기 위해서는 정렬할 데이터를 힙 구조로 변형해야 한다.

위쪽으로 보았을 때는 최대힙이 형성되어있으나 아래쪽으로보았을 때는 데이터 5를 가지는 노드 때문에 최대힙이 형성되어있지 않은 경우

☞ 해당 노드의 자식 노드 중 자신보다 큰 값과 위치를 변경(힙 생성 알고리즘 이용)

힙 생성 알고리즘(Heapify Algorithm)

특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 변경하는 알고리즘으로 한 번 위치를 바꾼 후 여전히 자식이 존재하는 경우 다시 자식 노드 중에서 더 큰 자식과 자신의 위치를 바꾸는 동작을 수행한다.

특정한 하나의 노드에 대해 수행하는 것으로 해당 하나의 노드를 제외하고는 최대 힙이 구성되어있는 상태가 가정되어 있어야 한다.

힙 생성 알고리즘의 시간 복잡도

데이터의 개수가 N개일 때 노드의 높이는 logN

한 번 자식 노드로 내려갈 때마다 노드의 개수가 2배씩 증가하기 때문에 O(logN)

하지만 실질적으로 비교에 필요한 노드의 개수는 N/2개이므로 결과적으로 시간 복잡도는 O(N)

힙 정렬 Sequence

더보기

순서대로 배열에 저장

 

힙 구조로 변경(상향식)

 

부모노드와 가장 마지막 집합의 노드를 변경

 

가장 마지막 노드를 제외한 노드만 이용해 힙 구조로 변경 + 부모노드와 집합의 가장 마지막 노드 위치 변경 동작 반복

 

결과

Code

#include <iostream>
using namespace std;
#define number 9

int heap[9] = {7, 6, 5, 8, 3, 5, 9, 1, 6};

int main(void){
    // 최대 힙 구조 만들기
    for(int i=1;i<number;i++){
        int c = i;
        do{
            // root: 자기 자신의 부모
            int root = (c - 1) / 2;
            // 부모의 값보다 자식의 값이 크면 두 원소 위치 변경
            if(heap[root] < heap[c]){
                int temp = heap[root];
                heap[root] = heap[c];
                heap[c] = temp;
            }

            // 자식의 부모로 이동해 반복적으로 힙 구조 만들기
            c = root;
        } while(c!=0);
    }

    // 크기를 줄여가며 반복적으로 힙 구성
    for(int i=number - 1;i>=0;i--){
        // root node와 가장 마지막 node의 위치 변경
        int temp = heap[0]; // 0번째 index = root node
        heap[0] = heap[i];
        heap[i] = temp;

        // 다시 최대 힙 구조 만들기
        int root = 0;
        int c = 1;
        do{
            // c: root의 자식
            c = 2 * root + 1;
            // 자식 중에 더 큰 값 찾기
            // 왼쪽과 오른쪽 중 더 큰 값을 c에 담음
            if(heap[c] < heap[c+1] && c < i - 1){
                // 왼쪽 값보다 오른쪽 값이 더 크면 오른쪽 node의 index가 c에 저장됨
                c++;
            }

            // root보다 자식이 더 크면 root와 자식을 교환
            if(heap[root] < heap[c] && c < i){
                int temp = heap[root];
                heap[root] = heap[c];
                heap[c] = temp;
            }
            // c를 root로 이동시켜 반복
            root = c;
        } while(c < i);
    }

    for(int i=0;i<number;i++)
        cout << heap[i] << ' ';
    return 0;
}

출력

1 3 5 5 6 6 7 8 9

시간 복잡도

항상 O(N*logN)의 시간 복잡도를 보장한다.