졍's 기술 블로그

단지번호붙이기

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

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제 입출력

Algorithm

BFS
1. 그래프 구현
2. 단지에 포함되어있고(graph[x][y] == 1), 방문한 적이 없다면(not visited[x][y]) bfs 수행
-> 이 때 home_cnt 라는 리스트에(각 단지의 아파트 개수) 마지막 원소(0) append
3. bfs 수행하면서 아파트 하나씩 만날 때 마다 home_cnt의 마지막 원소 증가
4. bfs 수행 완료 후 home_cnt의 마지막 원소가 0인 경우(시작 위치 제외하고 만난 아파트가 없는 경우) manually 1 증가
5. home_cnt 리스트 sort 후 length, 원소 하나씩 출력

Code

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

def bfs(graph, sx, sy, visited):
    queue.append((sx, sy))

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

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

            # graph 벗어나면 continue
            if nx < 0 or nx > N-1 or ny < 0 or ny > N-1:
                continue

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

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

            # 방문 기록
            cnt_home[-1] += 1
            visited[nx][ny] = True
            queue.append((nx,ny))
    
N = int(input())
graph = []
for i in range(N):
    graph.append(list(map(int, input())))

cnt_home = []
visited = [[False for _ in range(N)] for _ in range(N)]
for x in range(N):
    for y in range(N):
        queue.clear()
        if graph[x][y] and not visited[x][y]:
            cnt_home.append(0)
            bfs(graph, x, y, visited)
            if not cnt_home[-1]:
                cnt_home[-1] += 1

cnt_home.sort()
print(len(cnt_home))
for i in cnt_home:
    print(i)

메모리: 34184 KB
시간: 64 ms

미로 탐색

티어 : 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)