[KMU - algolab] c++ 프로그래밍 week 6 과제 풀이

algolab은 국민대학교 소프트웨어학부 수업에서 사용되는 온라인 저지?(과제 제출 사이트)입니다.

 

이전 주차들과 마찬가지로 6주차 과제 제출 기한이 끝났기 때문에, 한번 풀이를 작성해보겠습니다.

 

22. 행렬 곱셈

저번주에는 행렬 덧셈이 문제로 출제되었는데, 이번주는 행렬 곱셈이네요.

 

행렬곱셈은 소융 기준, 1학년 2학기에 배운 내용이니, 설명은 넘어가고 바로 코드부터 보겠습니다. 근데, 또또또 문제에서 주어진 테케가 이상(-가 ㅡ로 표기 되어있습니다.)하여서, 코드를 짜고 검증을 할 때, 이슈가 생겼습니다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int tc,a,b,c;
ll A[110][110];
ll B[110][110];
ll ans[110][110];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> tc;
    while(tc--) {
        cin >> a >> b >> c;
        for(int y=0; y<a; y++)
            for(int x=0; x<c; x++)
                ans[y][x] = 0;
        
        for(int y=0;y<a; y++) {
            for(int x=0; x<b; x++) {
                cin >> A[y][x];
            }
        }
        for(int y=0; y<b; y++) {
            for(int x=0; x<c; x++) {
                cin >> B[y][x];
            }
        }
        for(int x=0; x<a; x++) {
            for(int y=0; y<b; y++) {
                for(int z=0; z<c; z++) {
                   ans[x][z] += A[x][y] * B[y][z]; 
                }
            }
        }
        for(int y=0;y<a; y++) {
            for(int x=0; x<c; x++) {
                cout << ans[y][x] << " ";
            }
            cout << "\n";
        }
    }    
}

23. 방의 크기 구하기

이 문제는 할 말이 많습니다. 설명도 많이 필요할 듯하구요.

 

이 문제는 전형적인 DFS문제입니다.

하지만, 아직 DFS가 뭔지, 어떻게 구현하는 건지 잘 모르거나, 알더라도 응용은 잘 안되는 분들이 많은 것 같습니다.

아무리 python, java 같은 언어를 배웠더라도, 알고리즘을 배운건 아니니까요..

 

자, 다시 돌아와서, DFS 알고리즘은 사실 "알고리즘 공부를 시작했어!" 라고 말하면 바로 배우게 되는 알고리즘 중 하나입니다. DFS는 재귀함수를 활용하여 탐색을 하면서, 굉장히 쉽게 탐색을 구현할 수 있으며, 이를 최적화를 하는 방법에 대해서도 배울 수 있기때문이요.(제 개인적인 생각입니다 :) )

 

DFS를 다 설명하려면, 이건 문제 풀이가 아니라 DFS 알고리즘 설명이 될 것같아 DFS 자체 설명은 SKIP하고, code와 code가 어떻게 구성되었는가를 보겠습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned int uint;
typedef vector <ull> ullv1;
typedef vector <vector <ull>> ullv2;

ll tc,m,n,ans,cnt;
bool check[110][110];
string ar[110];
int dy[] = {0,0,1,-1};
int dx[] = {1,-1,0,0};
ullv1 ret;

void init() { // m = row, n = col
    cin >> n >> m;
    ans = 0; // 방의 개수
    cnt = 0; // 방의 넓이  
    ret.clear(); // 방의 넓이 담아 두는 벡터
    for(int x=0; x<m; x++) cin >> ar[x];
    for(int y=0; y<m; y++) {
        for(int x=0; x<n; x++) {
            check[y][x] = true; // 이 지점을 방문할 수 있는가? -> 이 지점을 이전에 방문한 적 있는가?를 판단하는 척도
        }
    }
}

void dfs(int Y,int X) {
    cnt++;
    check[Y][X] = false;
    for(int d = 0; d<4; d++) {
        int next_Y = Y + dy[d];
        int next_X = X + dx[d];
        if(0 >next_Y || 0>next_X || next_Y >= m || next_X >=n) continue;
        if(ar[next_Y][next_X] == '.' && check[next_Y][next_X]) dfs(next_Y,next_X);
    }
}

void solve() {
    for(int y=0; y<m; y++) {
        for(int x=0; x<n; x++) {
            if(ar[y][x] == '.' && check[y][x]) {
                cnt = 0;
                ans++;
                dfs(y,x);
                ret.push_back(cnt);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> tc;
    while(tc--) {
        init();
        solve(); 
        cout << ans << "\n";
        sort(ret.begin(),ret.end(),greater<ull> ());
        for(auto i : ret) {
            cout << i << " ";
        }
        cout<<"\n";
    }
}

제가 코드상으로 n과 m을 거꾸로 사용하였습니다. 주의해주세요..ㅠㅠ

 

main 함수는 굉장히 짧습니다.

1. init()이라는 함수는 변수 초기화, 입력들을 하는 함수입니다.
2. solve()라는 함수는 답을 구하는 함수(결론적으로는 dfs() 함수를 호출하면서 답을 구해내는 함수이겠죠)입니다.
3. 그 아래는 출력을 하는 부분입니다.
   1. ans : 방의 개수입니다. (ret.size()를 출력해도 상관없습니다.)
   2. ret: 방의 크기들을 담아놓는 vector입니다. 배열로 크기들을 담아놓아도 됩니다. (그냥 제가 vector 덕후입니다.)
   3. sort는 문제 상으로 내림차순 출력이라 추가해놓은 것입니다. "greater<unsigned long long> ()"의 의미를 모르시면 오름차순으로 그냥 sort 한 뒤에, 거꾸로 출력하셔도 됩니다. (설명하기 귀찮은 건...아닙니다.. 아마요..?)

자, 차례대로 init부터!

init은 따로 설명쓰기 귀찮아서, 주석으로 남겨놨습니다. :)

가장 중요한 건 check 배열의 의미입니다! 

이전에 방문했다면 fale를 저장하고 방문한적 없다면 true로 저장해놓은 배열이라는 것입니다.

 

그다음 solve()!

일단, DFS를 돌려서 방의 크기를 구해야 하는 것을 알고는 있는데, 문제는 어느 지점을 스타트 지점으로 잡고 DFS를 시작할지가 문제인 상황이죠? 그러면, 일단 모든 지점을 스타트 지점으로 삼아보는 것입니다. 단, 그 지점이 방 안('.')이고 이전에 방문한 적없는 곳이란 전제하에 말이죠.

 

그럼, 이런 지점을 기준으로 DFS를 돌리고, dfs 함수 내에서는 방문하고 있는 점을 기준으로 4방향을 탐색합니다. 그리고, 그 4지점이 현재 지도?를 벗어나지 않는지 또, 방 안인지, 이전에 방문한적이 없는 곳인지를 확인하고 다시, dfs 함수를 호출합니다. 그렇게 모든 점을 탐색하면 되는 것입니다.

 

최대한 간결하게 쓰려다보니, 내용이 많이 생략되었네요. 이상한게 있거나, 질문이 있으시면 댓글에 남겨주세여

 

아무튼, 결론적으로는 이 문제는 DFS 알고리즘을 통해서 O(n^2)의 시간복잡도를 가지고 모든 점을 탐색할 수 있게 됩니다.

 

한번, 이런 문제들을 풀어보시면 DFS를 연습해보실 수 있습니다.

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

13565번: 침투

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

1260번: DFS와 BFS

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

1743번: 음식물 피하기

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

4963번: 섬의 개수

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

2638번: 치즈

24. 괄호

이 문제는 "스택"을 활용할 줄 아는가에 대한 문제입니다.

개인적으로는, 배열로 직접 스택을 구현하고 풀까생각도 해봤다가, 오히려 더 설명하기가 어려울 것 같아서 STL stack을 활용했습니다.

 

이 문제 형식은 굉장히 유명한 스타일의 스택 다루기 문제입니다. 길게 설명할 것 없이 요약을 해보자면,

 

0) 괄호 문자열을 앞에서 부터 순서대로 살펴본다.

1) 여는 괄호인 경우, 일단 스택에 넣는다.

2) 닫는 괄호인 경우, 2가지의 경우로 분리하여 생각한다.

    2-1) 스택이 비어있거나, 스택의 top()의 괄호와 쌍이 맞지 않는 경우 -> invalid한 경우로 분류한다.

    2-2) 스택이 비어있지 않고, 스택의 top()의 괄호와 쌍이 맞는 경우

3) 모든 괄호를 다 살펴보고 나서, 스택이 비어있는지 확인한다. -> 비어있지 않다면, invalid한 경우로 분류한다.

 

+) 구현 시 주의 사항

1) 3번 과정을 하였는가?

2) 테케 형식의 문제임으로, 반복문 시작전에 stack을 비워주는 과정을 추가하였는가?

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned int uint;
typedef vector <ull> ullv1;
typedef vector <vector <ull>> ullv2;

stack <char> stk;
int tc;
int ans;
string s;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> tc;
    while(tc--) {
        while(!stk.empty()) stk.pop();
        ans = 1;
        cin >> s;

        for(int x=0; x<s.size(); x++) {
            switch (s[x])
            {
            case '(':
            case '[':
            case '{':
                stk.push(s[x]);
                break;
            case ')':
                if(stk.empty()) ans = 0;
                else {
                    if(stk.top() != '(') ans = 0;
                    else stk.pop();
                }
                break;
            case '}':
                if(stk.empty()) ans = 0;
                else {
                    if(stk.top() != '{') ans = 0;
                    else stk.pop();
                }
                break;
            case ']':
                if(stk.empty()) ans = 0;
                else {
                    if(stk.top() != '[') ans = 0;
                    else stk.pop();
                }
                break;
            }
        }
        if(!stk.empty()) ans = 0;
        cout << ans << "\n";
    }
}

이런 느낌의 문제로는 요런 문제들이 있습니다.

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

7585번: Brackets

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

4949번: 균형잡힌 세상

 

아무튼,

Rmx