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

1.문제설명

도시를 정복하기 위해 MST를 만들어야 하는 문제이다.

주의할 점은 한 도시를 정복한 이후부터 간선의 가중치가 t값만큼 증가해야한다.

첫 도시를 정복할 때 가중치가 포함되면 안된다.

Java로 Prim 알고리즘을 구현하기 위해서

자바 우선순위큐를 사용할 줄 알아야한다.

이때 custom class를 이용하기 때문에 Comparable을 implements 해주어야 한다.

2.문제풀이코드 C++

import java.util.*;

class Edge implements Comparable<Edge>{
//    boolean canUse;
    int x, y;
    Edge(int x, int y){
//        canUse = true;
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "(" + x + "," + y + ")";
    }

    @Override
    public int compareTo(Edge edge){
        return Integer.compare(y, edge.y);
    }
}

public class Main {
    static int n,m,t;
    static boolean ch[];
    static ArrayList<Edge> adj[];


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        t = sc.nextInt();

        PriorityQueue<Edge> Q = new PriorityQueue<>();
        ch = new boolean[n+1];


        adj = new ArrayList[n+1];
        for(int i=0; i<=n; i++){
            adj[i] = new ArrayList<Edge>();
        }


        for(int i=0; i<m; i++){
            int a, b, c;
            a = sc.nextInt();
            b = sc.nextInt();
            c = sc.nextInt();
            adj[a].add(new Edge(b,c));
            adj[b].add(new Edge(a,c));
        }


        Q.add(new Edge(1,0));

        int cnt = 0;
        int ans = 0;
        while(!Q.isEmpty()){
            Edge cur = Q.poll();

            if(!ch[cur.x]){
                ch[cur.x] = true;
                ans += cur.y;
                cnt++;

                if(cnt>2){
                    ans += t*(cnt-2);
                }

//                System.out.println(ans);

                for(Edge nx : adj[cur.x]) {
                    if (ch[nx.x] == false) {
                        Q.add(nx);
                    }
                }
            }
        }

        System.out.println(ans);

    }
}

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

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Point{
    int x, y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "(" + x + "," + y + ")";
    }
}

public class Main {

    static int dx[] = {1,0,-1,0};
    static int dy[] = {0,1,0,-1};
    static int map[][] = new int[101][101];

    static Queue<Point> Q = new LinkedList<>();
    static Queue<Point> willDisappear = new LinkedList<>();

    static boolean isContact(int x, int y){
        int cnt = 0;
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || nx>n || ny<0 || ny>m) continue;
            if(map[nx][ny]==-1){
                cnt++;
            }
        }
        if(cnt>=2) return true;
        else return false;
    }

    static int n,m;

    static void spreadAir(){
        while(!Q.isEmpty()){
            Point cur = Q.poll();

            for(int i=0; i<4; i++){
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if(nx<0 || nx>n || ny<0 || ny>m) continue;
                if(map[nx][ny]==0){
                    map[nx][ny] = -1;
                    Q.add(new Point(nx, ny));
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for(int i=0; i<n; i++){
            for(int j=0;j<m; j++){
                map[i][j] = sc.nextInt();
            }
        }

        Q.add(new Point(0,0));
        Q.add(new Point(0,m-1));
        Q.add(new Point(n-1,0));
        Q.add(new Point(n-1,m-1));
        spreadAir();

        int ans = 0;
        while(true){
            boolean flag = false;
            for(int i=0; i<n; i++){
                for(int j=0;j<m; j++){
                    if(map[i][j] == 1){
                        flag = true;
                        if(isContact(i,j)){
                            willDisappear.add(new Point(i,j));
                        }
                    }
                }
            }


            if(flag==false) break;

            while(!willDisappear.isEmpty()){
                Point curr = willDisappear.poll();
                map[curr.x][curr.y] = -1;
                Q.add(curr);
            }
            spreadAir();
            ans++;
        }

        System.out.println(ans);

    }
}

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

1. DFS 풀이

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    static boolean ch[] = new boolean[501];
    static LinkedList[] adj = new LinkedList[501];
    static boolean flag = false;

    static void DFS(int cur, int pre){
        for(Object a: adj[cur]){
            if(ch[(int)a]==true){
                if((int)a!=pre)flag = true;
            }
            else{
                ch[(int)a] = true;
                DFS((int)a, cur);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int trial = 1;
        while(true){
            int n = sc.nextInt();
            int k = sc.nextInt();
            if(n==0) break;
            int trees = 0;
            Arrays.fill(ch,false);

            for(int i=0; i<n+1; i++){
                adj[i] = new LinkedList<Integer>();
            }

            for(int i=0; i<k; i++){
                int n1 = sc.nextInt();
                int n2 = sc.nextInt();
                adj[n1].add(n2);
                adj[n2].add(n1);
            }


            for(int i=1; i<=n; i++){
                flag = false;
                if(ch[i]==false){
                    ch[i] = true;
                    DFS(i, 0);
                    if(!flag) {
                        trees+=1;
                    }
                }
            }

            if(trees>1){
                System.out.printf("Case %d: A forest of %d trees.\n",trial, trees);
            }
            else if(trees==1) {
                System.out.printf("Case %d: There is one tree.\n",trial);
            }
            else{
                System.out.printf("Case %d: No trees.\n", trial);
            }

            trial+=1;
        }
    }
}

2.Union&Find

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {

    static int[] unf = new int[501];

    static int Find(int a){
        if(unf[a] < 0) return a;
        else return unf[a] = Find(unf[a]);
    }

    static void Union(int a, int b){
        a= Find(a);
        b = Find(b);
        if(a!=b){
            if(unf[a]==-2){
                unf[b] = a;
            }
            else if(unf[b]==-2){
                unf[a] = b;
            }
            else if(unf[a] < 0){
                unf[b] = a;
            }
            else {
                unf[a] = b;
            }
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int trial = 1;


        while(true){
            Arrays.fill(unf,-1);
            int n = sc.nextInt();
            int k = sc.nextInt();
            if(n==0) break;
            int trees = 0;


            for(int i=0; i<k; i++){
                int n1 = sc.nextInt();
                int n2 = sc.nextInt();

                n1 = Find(n1);
                n2 = Find(n2);

                if(n1==n2){
                    unf[n1] = -2;
                }
                else{
                    Union(n1,n2);
                }
            }

            for(int i=1; i<=n; i++){
                if(unf[i]==-1) trees+=1;
            }

            if(trees>1){
                System.out.printf("Case %d: A forest of %d trees.\n",trial, trees);
            }
            else if(trees==1) {
                System.out.printf("Case %d: There is one tree.\n",trial);
            }
            else{
                System.out.printf("Case %d: No trees.\n", trial);
            }

            trial+=1;
        }
    }
}

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

중앙값을 다이렉트하게 뽑아낼 수 있는 자료구조 라이브러리는 존재하지 않는다.

하지만 우선순위 큐 두개를 이용해서 중앙값을 적은 cost로 뽑아 낼 수 있다.

import java.util.*;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());

        for(int T=0; T<t; T++){
            maxHeap.clear();
            minHeap.clear();
            int n = Integer.parseInt(br.readLine());
            bw.write((n/2 + 1) + "\n");
            int lines = n%10==0 ? n/10 : n/10 + 1;
            int cnt = 0;
            int printed = 0;
            for(int i=0; i<lines; i++){
                String[] split = br.readLine().split(" ");

                for(int j=0; j<split.length;j++){
                    int cur = Integer.parseInt(split[j]);
                    if(cnt==0){
                        minHeap.add(cur);
                    }
                    else{
                        if(cur<=minHeap.peek()){
                            maxHeap.add(cur);
                        }
                        else {
                            minHeap.add(cur);
                        }
                    }
                    cnt++;


                    if(cnt%2==1){
                        while(maxHeap.size() >= minHeap.size()){
                            minHeap.add(maxHeap.peek());
                            maxHeap.poll();
                        }

                        while(maxHeap.size() + 1 < minHeap.size()){
                            maxHeap.add(minHeap.peek());
                            minHeap.poll();
                        }
                        bw.write(minHeap.peek().toString() + " ");

                        printed++;

                        if(printed%10==0) bw.write("\n");
                    }

                }
            }
            bw.write("\n");
        }
        bw.flush();
    }
}

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

#include <bits/stdc++.h>
using namespace std;

int n, a,b,c, a2,b2,c2, maxx[3], minn[3];
int main() {

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> a >> b >> c;
		a2 = a;
		b2 = b;
		c2 = c;

		a = a + max(maxx[0], maxx[1]);
		b = b + max({ maxx[0], maxx[1], maxx[2] });
		c = c + max(maxx[2], maxx[1]);

		maxx[0] = a;
		maxx[1] = b;
		maxx[2] = c;


		a2 = a2 + min(minn[0], minn[1]);
		b2 = b2 + min({ minn[0], minn[1], minn[2] });
		c2 = c2 + min(minn[2], minn[1]);

		minn[0] = a2;
		minn[1] = b2;
		minn[2] = c2;
	}

	cout << max({ maxx[0], maxx[1], maxx[2]}) << ' ' << min({minn[0],minn[1],minn[2]});


	return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

int color[20001];
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int k;
	cin >> k;
	for (int T = 0; T < k; T++) {
		int v, e;
		cin >> v >> e;

		memset(color, 0, sizeof(color));

		vector<int> adj[20001];
		for (int i = 0; i < e; i++) {
			int a, b;
			cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		queue<int> Q;

		bool flag = true;

		for (int i = 1; i <= v; i++) {
			if (color[i] == 0) {
				color[i] = 1;
				Q.push(i);
	
				while (!Q.empty()) {
					int x = Q.front();
					int cc = color[x];
					Q.pop();

					for (auto nx : adj[x]) {
						if (color[nx] == cc) {
							flag = false;
							cout << "NO\n";
							break;
						}
						else if (color[nx] == 0) {
							color[nx] = cc == 1 ? 2 : 1;
							Q.push(nx);
						}
					}

					if (!flag) break;
				}

				if (!flag) break;
			}
		}


		if (flag) {
			cout << "YES\n";;
		}


	}

	return 0;
}

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

1. 문제설명

간선의 cost를 뺏기는 양으로 두면

금을 땅에서 주울 경우에는 마이너스

뺏길 경우는 플러스로 두게 되어 이동하는데 필요한 cost를 설정할 수 있다.

이후 벨만포드 알고리즘을 적용해서 풀면 된다.

단 이 문제의 경우 음의 사이클이 존재한다고 무조건 -1이 될 수 없다.

왜냐하면 음의 사이클이 존재해도 시작점에서 도착점까지 가는데 경유하지 않을 수 있기 때문이다

즉 음의사이클이 존재는 하나 따로 동떨어진 경우가 테스트케이스로 들어올 수도 있다.

그래서 음의사이클이 존재하고 음의사이클에서 도착점으로 가는지 판단해야한다.

또한 출발점 1에서 도착점 n까지 도달할 수 있는지 확인해야한다.

이를 위해 역방향 간선을 저장해두고 n으로부터 시작하여 BFS를 돌면

1과 음의 사이클에서 도착점까지 갈 수 있는지 확인할 수 있다.

2. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;

const long long INF = 1e18;
long long dist[101];
int pre[101];

int n, m;
vector<pi> adj[101];
vector<pi> rev_adj[101];

bool goal[101];

void check_goal() {
	queue<int> Q;

	Q.push(n);
	goal[n] = 1;

	while (!Q.empty()) {
		int x = Q.front(); Q.pop();
		for (auto &i : rev_adj[x]) {
			int nx = i.first;
			if (goal[nx] == 0) {
				Q.push(nx);
				goal[nx] = 1;
			}
		}
	}
}

void print(int n) {

	if (n == 0) return;
	print(pre[n]);
	cout << n << ' ';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({ v,-w });
		rev_adj[v].push_back({ u,-w });
	}
	
	check_goal();

	//시작점에서 도착점 가는 길이 없는 경우
	if (goal[1] == 0) {
		cout << -1 << '\n';
		return 0;
	}

	fill(dist, dist + 101, INF);

	dist[1] = 0;



	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= n; j++) {

			for (auto& a : adj[j]) {
				int nx = a.first;
				int d = a.second;

				if (dist[j] != INF && dist[nx] > dist[j] + d) {
					pre[nx] = j;
					dist[nx] = dist[j] + d;

					if ((i == n-1) && (goal[j])) {
						cout << -1 << '\n';
						return 0;
					}
				}
			}
		}
	}


	print(n);


	return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

int arr[1001][1001];
int psum[1001][1001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;


	//좌표 압축 
	vector<pair<int, int> > v;
	set<int> s_x;
	set<int> s_y;
	map<int, int> m_x;
	map<int, int> m_y;

	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		v.push_back({ x,y });
		s_x.insert(x);
		s_y.insert(y);
	}

	int idx = 1;

	for (auto i : s_x) {
		m_x[i] = idx++;
	}

	idx = 1;

	for (auto i : s_y) {
		m_y[i] = idx++;
	}


	for (int i = 0; i < n; i++) {
		arr[m_x[v[i].first]][m_y[v[i].second]] = 1;
	}



	//사분면 누적합 구하기 
	int ans = INT_MAX;


	for (int i = 0; i < 1000; i++) {
		for (int j = 0; j < 1000; j++) {
			psum[i + 1][j + 1] = psum[i + 1][j] + psum[i][j + 1] - psum[i][j] + arr[i+1][j+1];
		}
	}


	for (int i = 0; i < 1000; i++) {
		for (int j = 0; j < 1000; j++) {

			int a = psum[i][j];
			int b = psum[i][1000] - a;
			int c = psum[1000][j] - a;
			int d = psum[1000][1000] - a - b - c;

			ans = min(ans, max({ a, b, c, d }));
		}
	}
	cout << ans << '\n';

	return 0;
}