www.acmicpc.net/problem/1967

 

1967번: 트리의 지름

파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연

www.acmicpc.net

 

 

[난이도] Gold4

[유형] 트리의 지름(DFS)

 

[풀이] 

트리의 지름 : 트리에서 거리가 가장 먼 두 점 사이의 거리. 구

하는 방법 : 임의의 점에서 DFS로 가장 먼 점을 찾은 뒤에 그 점에서 DFS를 이용해서 가장 먼 점을 찾으면 그 거리가 트리의 지름이 된다.

 

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int N,ans,mxN,mxV;
bool visit[10001];
vector<pair<int,int>> adj[10001];
void dfs(int n,int c){
    visit[n] = 1;
    if(c>mxV){
        mxV=c;
        mxN=n;
    }
    for(auto nxt : adj[n]){
        if(!visit[nxt.first]) dfs(nxt.first,c+nxt.second);
    }
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N-1;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    dfs(1,0);
    memset(visit,0,sizeof(visit));
    mxV=0;
    dfs(mxN,0);
    printf("%d",mxV);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1967.cpp

 

www.acmicpc.net/problem/17779

 

17779번: 게리맨더링 2

재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름

www.acmicpc.net

 

 

[난이도] Gold4

[유형] Brute force, DFS (삼성SW기출)

 

[풀이]

1. 문제의 주어진 조건에 따라 5선거구의 경계를 체크한다.

2. (1,1)은 1선거구, (1,N)은 2선거구, (N,1)은 3선거구 (N,N)은 4선거구에 각각 무조건 포함되므로 4개의 점에서 DFS를 수행하면서 각 선거구의 인구를 구한다.

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int N,map[21][21],A[21][21],total,ans=1e8;
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,1,-1};
bool check(int d1,int d2,int x,int y){
    bool r = d1 >= 1 && d2 >= 1 && 1 <= x && x < x+d1+d2 && x+d1+d2 <= N;
    bool c = 1 <= y-d1 && y-d1 < y && y < y+d2 && y+d2 <=N;
    return r&&c;
}
void mask(int d1,int d2,int x,int y){
    int sx,sy,dx,dy;

    sx=x,sy=y,dx=1,dy=-1;
    for(int i=0;i<=d1;i++) {
        map[sx][sy] = 1;
        sx+=dx,sy+=dy;
    }
    sx=x,sy=y,dx=1,dy=1;
    for(int i=0;i<=d2;i++) {
        map[sx][sy] = 1;
        sx+=dx,sy+=dy;
    }
    sx=x+d1,sy=y-d1,dx=1,dy=1;
    for(int i=0;i<=d2;i++) {
        map[sx][sy] = 1;
        sx+=dx,sy+=dy;
    }  
    sx=x+d2,sy=y+d2,dx=1,dy=-1;
    for(int i=0;i<=d1;i++) {
        map[sx][sy] = 1;
        sx+=dx,sy+=dy;
    }     
}

int dfs(int d1,int d2,int x,int y,int r,int c,int k){
    if(k==1){
        if(!(1<=r&&r<x+d1&&1<=c&&c<=y)) return 0;
    }else if(k==2){
        if(!(1<=r&&r<=x+d2&&y<c&&c<=N)) return 0;
    }else if(k==3){
        if(!(x+d1<=r&&r<=N&&1<=c&&c<y-d1+d2)) return 0;
    }else if(k==4){
        if(!(x+d2<r&&r<=N&&y-d1+d2<=c&&c<=N)) return 0;
    }
    map[r][c] = k;
    int ret = A[r][c];
    for(int i=0;i<4;i++){
        int nr = r+dx[i];
        int nc = c+dy[i];
        if(nr < 1 || nc < 1 || nr > N || nc > N || map[nr][nc]) continue; 
        ret += dfs(d1,d2,x,y,nr,nc,k);
    }
    return ret;
}

int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) {
            scanf("%d",&A[i][j]);
            total+=A[i][j];
        }

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            for(int d1=1;d1<=N;d1++){
                for(int d2=1;d2<=N;d2++){
                    if(!check(d1,d2,i,j)) continue;
                    memset(map,0,sizeof(map));
                    mask(d1,d2,i,j);
                    int sx = 1,sy=1;
                    vector<int> sum;
                    sum.push_back(dfs(d1,d2,i,j,1,1,1));
                    sum.push_back(dfs(d1,d2,i,j,1,N,2));
                    sum.push_back(dfs(d1,d2,i,j,N,1,3));
                    sum.push_back(dfs(d1,d2,i,j,N,N,4));
                    int rm = total;
                    for(int i=0;i<4;i++) rm -= sum[i];
                    sum.push_back(rm);
                    sort(sum.begin(),sum.end());
                    ans = min(ans,sum.back()-sum.front());
                }
            }
        }
    }    
    printf("%d",ans);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/17779.cpp

 

www.acmicpc.net/problem/1043

 

1043번: 거짓말

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게

www.acmicpc.net

 

 

[난이도] Gold4

[유형] DFS

 

[풀이]

지민이는 진실을 아는 사람이 있는 파티에서는 거짓말을 못한다. 어떤 파티에서 진실을 아는 사람이 있어서 진실을 말하면 그 파티에 참여한 진실을 모르는 사람이 참여한 모든 파티에서도 거짓말을 할 수 없다. 즉, 지민이가 진실을 말한 파티에 있는 모든 사람들은 진실을 아는거나 마찬가지이다. 이 성질을 이용하여 진실을 아는 사람들을 DFS를 이용하여 갱신해주면 답을 구할 수 있다.

 

#include <cstdio>
#include <vector>
using namespace std;
int N,M;
vector<int> pp[51],pty[51],tp;
bool visit[51];
void dfs(int n){
    visit[n] = 1;
    for(auto ptn : pp[n]){
        for(auto p : pty[ptn]){
            if(!visit[p]) dfs(p);
        }
    }
}
int main(){
    scanf("%d%d",&N,&M);
    int t,v;
    scanf("%d",&t);
    for(int i=0;i<t;i++) {
        scanf("%d",&v);
        tp.push_back(v);
    }
    for(int i=1;i<=M;i++){
        scanf("%d",&t);
        for(int j=0;j<t;j++){
            scanf("%d",&v);
            pty[i].push_back(v);
            pp[v].push_back(i);
        }
    }

    for(auto a : tp) dfs(a);
    int ans = 0;
    for(int i=1;i<=M;i++){
        bool ok = 1;
        for(auto p : pty[i]) {
            if(visit[p]){
                ok = 0;
                break;
            }
        }
        if(ok) ans++;
    }
    printf("%d",ans);
}

 

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1043.cpp

https://leetcode.com/problems/count-good-nodes-in-binary-tree/

 

Count Good Nodes in Binary Tree - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

[풀이]

 

1. 재귀를 이용해서 이진트리의 모든 노드들을 순회한다.

2. 파라미터 v는 현재 node의 부모 node들의 value 중에 가장 큰 value를 의미한다.

3. 현재 노드의 value가 v보다 크면 return 값에 1을 더해 주어 결과값에 추가될 수 있도록 한다.

4. root는 무조건 추가되어야 하므로 main에서 -100000을 v에 넣어준다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

	int search(TreeNode* node, int v) {

		if (node == nullptr) return 0;
 
		int ret = 0;
		int cur_max = v;
		if (node->val >= v) {
			cur_max = node->val;
			ret++;
		}
		ret += search(node->left,  cur_max);
		ret += search(node->right, cur_max);

		return ret;
	}

	int goodNodes(TreeNode* root) {
		return search(root, -100000);
	}
};

https://github.com/has2/Algorithm/blob/master/leetcode/1448.cpp

+ Recent posts