파닭먹고싶다

문제 - https://www.acmicpc.net/problem/13460

import java.io.*;
import java.util.*;

public class Main {

    static int N, M, answer=-1;
    static char[][] board;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    static Queue<int[]> queue;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        board = new char[N][M];

        int[] init = new int[6]; // cnt, way, Rr, Rc, Br, Bc
        for (int i = 0; i < N; i++) {
            board[i] = br.readLine().toCharArray();
            for (int j = 0; j < M; j++)
                if (board[i][j]=='R') { // R의 위치를 저장
                    init[2] = i;
                    init[3] = j;
                    board[i][j]='.';
                }
                else if (board[i][j]=='B') { // B의 위치를 저장
                    init[4] = i;
                    init[5] = j;
                    board[i][j]='.';
                }
        }

        queue = new LinkedList();
        for (int i = 0; i < 4; i++)
            queue.add(new int[]{1, i, init[2], init[3], init[4], init[5]}); // 각자의 위치에서 4방향으로 기울이는경우를 Q에 추가

        while (!queue.isEmpty()){
            int[] cur = queue.poll(); // 큐에서 하나씩 뽑아오며
            if (tilt(cur[0], cur[1], cur[2], cur[3], cur[4], cur[5])) // 기울이고, true가 나오면
                break;
        }
        bw.write(answer+"\n"); // 출력

        bw.flush();
        bw.close();
        br.close();
    }
    static boolean tilt(int cnt, int way, int Rr, int Rc, int Br, int Bc){ // 각 위치에서 way방향으로 cnt번째 출발.
        if(cnt>10) // 10번 넘으면 X
            return false;
        // 이동 시작.
        int[] p;
        if((way==0 && Rr<Br) || (way==1 && Rc>Bc) || (way==2 && Rr>Br) || (way==3 && Rc<Bc)){// 빨강 먼저 출발
            p = move(way, Rr, Rc); // 이동한 빨강 좌표
            Rr = p[0];
            Rc = p[1];
            p = move(way, Br, Bc); // 이동한 파랑 좌표
            Br = p[0];
            Bc = p[1];
            if(board[Br][Bc]=='O') // 파랑이 목적지 도착? -> 실패.
                return false;
            if(Rr==Br && Rc==Bc) { // 빨강 파랑이 겹치면, 빨강이 먼저 출발했으니 파랑이 뒤로가기.
                Br-=dr[way];
                Bc-=dc[way];
            }
        }
        else{ // 파랑 먼저 출발
            p = move(way, Br, Bc); // 이동한 파랑 좌표
            Br = p[0];
            Bc = p[1];
            p = move(way, Rr, Rc); // 이동한 빨강 좌표
            Rr = p[0];
            Rc = p[1];
            if(board[Br][Bc]=='O') // 파랑이 목적지 도착? -> 실패.
                return false;
            if(Rr==Br && Rc==Bc) { // 빨강 파랑이 겹치면, 파랑이 먼저 출발했으니 빨강이 뒤로가기.
                Rr-=dr[way];
                Rc-=dc[way];
            }
        }
        if(board[Rr][Rc]=='O') { // 빨강이 목적지 도착? -> O
            answer = cnt;
            return true;
        }
        for (int i = 0; i < 4; i++)
            if (i!=way)
                queue.add(new int[]{cnt+1, i, Rr, Rc, Br, Bc}); // 이동한 지점으로부터 온 방향을 제외하고 3가지 방향으로 다시 출발
        return false;
    }
    static int[] move(int way, int r, int c){
        int y = dr[way], x = dc[way];
        while (board[ r+y ][ c+x ]!='#'){ // 다음 목적지가 #가 아니라면 계속 전진.
            r += y;
            c += x;
            if (board[r][c]=='O') // 목적지에 도착하면 멈춤
                break;
        }
        return new int[]{r, c}; // 도착한 곳의 좌표 반환
    }
}

개인적으로, 공개된 난이도에 비해 어려웠던것같다.

파랑공과 빨강공의 이동순서 혹은 겹쳤을때의 예외처리에 대해서 고민하는데 한참걸린것같다.

그래도 Python에 비해서 Java가 BFS구현은 훨씬 용이한 것 같다.

문제 - https://www.acmicpc.net/problem/14889

import java.io.*;
import java.util.*;

public class Main {

    static int N;
    static int answer = Integer.MAX_VALUE;
    static int allstat;
    static int[] statsum;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine()); // 입력부분
        int[][] stat = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                stat[i][j] = Integer.parseInt(st.nextToken());
                allstat += stat[i][j]; // 배열의 전체 합
            }
        }

        statsum = new int[N]; // i번째 행과 열의 합을 저장하는 배열
        for (int i = 0; i < N; i++) {
            int tmp = 0;
            for (int j = 0; j < N; j++)
                if(i!=j)
                    tmp += stat[i][j] + stat[j][i];
            statsum[i] = tmp;
        }

        combination(new boolean[N], 0, N/2); // n/2개 만큼을 뽑는 경우의 수
        bw.write(answer+"\n");

        bw.flush();
        bw.close();
        br.close();
    }
    static void combination(boolean[] chk, int start, int remain){
        if (remain==0){ // n/2개 선택하면
            int sum = 0;
            for (int i = 0; i < N; i++)
                if(chk[i])
                    sum += statsum[i]; // 선택된것들의 합을 구하여

            answer = Math.min(answer, Math.abs(allstat - sum)); // 최솟값 갱신
            return;
        }

        for (int i = start; i < N-remain; i++) { // 재귀호출로 조합구현
            chk[i] = true;
            combination(chk, i+1, remain-1);
            chk[i] = false;
        }
    }
}

N개에서 N/2개 만큼 고르는 조합을 구하고,

이 조합에서 고르는 번호를 i라 할때,

배열의 전체합에서 i 번째 행과 열의 합을 빼주면 두 팀의 능력치합의 차이를 구할 수 있다.

이것을 이용하여 복잡한 연산없이 구할 수 있었다.

다만 Python 이었다면,

from itertools import combination as combi
for case in combi(arr, n//2):
	~~~~

이렇게 구했을 조합을 Java에서는 조금 힘들게(?) 구하는 법을 알았다.

문제 - https://www.acmicpc.net/problem/3860

import java.io.*;
import java.util.*;

public class Main {

    static final int MAX = Integer.MAX_VALUE;
    static class Point{
        int r, c;
        public Point(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    static class Edge{
        Point from, to;
        int cost;
        public Edge(Point from, Point to, int cost){
            this.from = new Point(from.r, from.c);
            this.to = new Point(to.r, to.c);
            this.cost = cost;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int W = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());
        int[] dr = {-1, 0, 1, 0};
        int[] dc = {0, 1, 0, -1};
        int[][] state, dist;
        ArrayList<Edge> edges;
        
        while (W!=0 && H!=0){
            edges = new ArrayList<>();
            state = new int[H][W];
            dist = new int[H][W];
            for (int i = 0; i < H; i++)
                Arrays.fill(dist[i], MAX);
            dist[0][0] = 0;
            
            int G = Integer.parseInt(br.readLine());
            for (int i = 0; i < G; i++) {
                st = new StringTokenizer(br.readLine());
                int c = Integer.parseInt(st.nextToken());
                int r = Integer.parseInt(st.nextToken());
                state[r][c] = 1;
            }
        
            int E = Integer.parseInt(br.readLine());
            for (int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine());
                int c1 = Integer.parseInt(st.nextToken());
                int r1 = Integer.parseInt(st.nextToken());
                int c2 = Integer.parseInt(st.nextToken());
                int r2 = Integer.parseInt(st.nextToken());
                int t = Integer.parseInt(st.nextToken());
                state[r1][c1] = -1;
                edges.add(new Edge(new Point(r1, c1), new Point(r2, c2), t));
            }

            for (int r = 0; r < H; r++)
                for (int c = 0; c < W; c++)
                    if (state[r][c]==0 && (r!=H-1 || c!=W-1))
                        for (int k = 0; k < 4; k++) {
                            int nr = r + dr[k];
                            int nc = c + dc[k];
                            if ((0 <= nr && nr < H) && (0 <= nc && nc < W) && state[nr][nc] != 1)
                                edges.add(new Edge(new Point(r, c), new Point(nr, nc), 1));
                        }

            for (int i = 0; i < W*H-G-1; i++)
                for (Edge e : edges)
                    if (dist[e.from.r][e.from.c] != MAX)
                        dist[e.to.r][e.to.c] = Math.min(dist[e.to.r][e.to.c], dist[e.from.r][e.from.c]+e.cost);

            never:{
                for (Edge e : edges)
                    if (dist[e.from.r][e.from.c] != MAX && dist[e.to.r][e.to.c] > dist[e.from.r][e.from.c]+e.cost) {
                        bw.write("Never\n");
                        break never;
                    }
                if(dist[H-1][W-1]==MAX)
                    bw.write("Impossible\n");
                else
                    bw.write(dist[H-1][W-1]+"\n");
            }
            
            st = new StringTokenizer(br.readLine());
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

Bellman-Ford 알고리즘을 이용하면 로직자체는 크게 어렵지 않게 구현할 수 있었다.

다만, 그럼에도 불구하고 계속해서 틀려서 뭐가 문제인지 한참을 고민했다.

문제는 도착점에서 Edge를 생성하면 안된다는 것이었다.

사실 왜 생성하면 안되는건지 아직 잘 납득이 안된다...

그보다 더 궁금한건, 다른 사람들의 풀이를 보았는데 나와 런타임차이가 약 2배가량나서 원인을 찾고자 코드를 뜯어봤다.

결과적으로 구체적으로 원인은 못찾겠지만, 자바는 메인에서 처리하는것보다 함수형으로 처리하는게 더 빠른 것 같다.

문제 - https://www.acmicpc.net/problem/11400

import java.io.*;
import java.util.*;

public class Main {

    static int V, E;
    static class Node{
        int order;
        ArrayList<Integer> link;
        public Node(){
            this.link = new ArrayList<>();
        }
    }static Node[] nodes;
    static ArrayList<int[]> answer = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        nodes = new Node[V+1];
        for (int i = 1; i <= V; i++)
            nodes[i] = new Node();

        E = Integer.parseInt(st.nextToken());
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            nodes[start].link.add(end);
            nodes[end].link.add(start);
        }

        dfs(1, 1);

        answer.sort( (a, b) -> a[0]==b[0] ? a[1]-b[1] : a[0]-b[0] );
        bw.write(answer.size()+"\n");
        for (int[] edge : answer)
            bw.write(edge[0]+" "+edge[1]+"\n");

        bw.flush();
        bw.close();
        br.close();
    }

    static int cnt=1;
    static int dfs(int id, int parent){
        if(nodes[id].order==0)
            nodes[id].order = cnt++;

        int ret = nodes[id].order;
        for(int next : nodes[id].link){
            if (next==parent)
                continue;

            if (nodes[next].order==0){
                int low = dfs(next, id);
                if(low>nodes[id].order)
                    answer.add( (id<next) ? new int[]{id, next} : new int[]{next, id});
                ret = Math.min(ret, low);
            }
            else
                ret = Math.min(ret, nodes[next].order);
        }
        return ret;
    }
}

단절점 문제와 크게 다른게 없다.

오히려 root node를 신경써주지 않아도 되서 더 단순한 형태다.

다만, 정렬에서 애를 먹었다.

파이썬이었으면 그냥

print(len(answer))
for a, b in sorted(answer, key=lambda x:(x[0], x[1])): # 사실 그냥 sorted(answer)만 해줘도 문제없다
	print(a, b)

이렇게만 처리해줘도 문제없이 답이 나올텐데, Java는 정렬이 너무 번거로운 것 같다.

java에서의 람다식과 3항연산에 익숙해져야겠다.

문제 - https://www.acmicpc.net/problem/11404

import java.io.*;
import java.util.*;

public class Main {

    static int N, M;
    static int[][] dist;
    static final int MAX = 10000000;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        dist = new int[N+1][N+1];
        for (int i = 1; i <= N; i++)
            Arrays.fill(dist[i], MAX);

        M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            dist[u][v] = Math.min(dist[u][v], w);
        }

        for (int k = 1; k <= N; k++)
            for (int u = 1; u <= N; u++)
                for (int v = 1; v <= N; v++)
                    dist[u][v] = Math.min(dist[u][v], dist[u][k] + dist[k][v]);

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i==j || dist[i][j]==MAX) bw.write(0+" ");
                else bw.write(dist[i][j] + " ");
            }
            bw.write("\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

}

로직에는 문제가 없는거같은데 제출만하면 자꾸 틀렸다고 떠서 한참을 고민했다.

입력을 받는 부분에서 중복이 있을 수 있는것을 고려하지 못했다.

ex) 1->2는 10 이 이미 있는데 1->2는 15가 추가로 들어와서 초기 dist[1][2]가 10이 아닌 15로 된다던지...

이 부분을 제외하고는 플로이드-워셜 알고리즘을 이용한 기초 문제이지 않나 싶다.

문제 - https://www.acmicpc.net/problem/11657

import java.io.*;
import java.util.*;

public class Main {

    static int N, M;
    static long[] dist;
    static final int MAX = Integer.MAX_VALUE;
    static class Edge{
        int from, to, cost;
        public Edge(int from, int to, int cost){
            this.from = from;
            this.to = to;
            this.cost = cost;
        }
    }static Edge[] edges;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        dist = new long[N+1];
        edges = new Edge[M];
        for (int i = 2; i <= N; i++)
            dist[i] = MAX;

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edges[i] = new Edge(a, b, c);
        }

        for (int i = 0; i < N-1; i++)
            for (Edge E : edges)
                if(dist[E.from]<MAX)
                    dist[E.to] = Math.min(dist[E.to], dist[E.from]+E.cost);

        if (!isCycle())
            for (int i = 2; i <= N; i++)
                if (dist[i]<MAX)
                    bw.write(dist[i]+"\n");
                else
                    bw.write("-1\n");
        else
            bw.write("-1\n");

        bw.flush();
        bw.close();
        br.close();
    }
    static boolean isCycle(){
        for (Edge E : edges)
            if(dist[E.from]!=MAX && dist[E.from]+E.cost < dist[E.to])
                return true;
        return false;
    }
}

기초 Bellman-Ford 알고리즘이다. 그런데 출력초과로 한참을 벙쪄있었다.

-10,000인 음의 간선이 존재할때, 최대 반복수가 500*6,000이므로 3,000,000*-10,000 이므로 -30,000,000,000이 되어 long타입이 아닌 int타입으로 dist배열을 선언하면 언더플로우가 발생한다.

오버플로우 말고 언더플로우는 처음겪어본다.

아무쪼록 Python을 제외한 언어에서는 문제조건을 보고 자료형에 조금 더 신경써야겠다.

문제 - https://www.acmicpc.net/problem/1753

import java.io.*;
import java.util.*;

public class Main {

    static int V, E, K;
    static class edge{
        int to, weight;
        public edge(int to, int weight){
            this.to = to;
            this.weight = weight;
        }
    } static ArrayList<edge>[] nodes;
    static final int MAX = 200000;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        nodes = new ArrayList[V+1];
        for (int i = 1; i <= V; i++)
            nodes[i] = new ArrayList<edge>();

        E = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(br.readLine());
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            nodes[u].add(new edge(v, w));
        }

        int[] dist = new int[V+1];
        for (int i = 1; i <= V; i++)
            if(i!=K) dist[i] = MAX;

        PriorityQueue<edge> pq = new PriorityQueue<>((a, b)->a.weight-b.weight);
        pq.add(new edge(K, 0));
        
        while (!pq.isEmpty()){
            edge now = pq.poll();
            if(now.weight > dist[now.to])
                continue;

            for (edge next : nodes[now.to])
                if (dist[next.to] > now.weight + next.weight){
                    dist[next.to] = now.weight + next.weight;
                    pq.add(new edge(next.to, dist[next.to]));
                }
        }

        for (int i = 1; i <= V; i++)
            if (dist[i]<MAX)
                bw.write(dist[i]+"\n");
            else
                bw.write("INF\n");

        bw.flush();
        bw.close();
        br.close();
    }
}

일반적으로 사용하던 dijkstra와는 조금 다른 방식으로 해서 낯설었다.

조금 더 시간복잡도면에서 효율적이니 이 방법 또한 익혀둬야겠다.

문제 - https://www.acmicpc.net/problem/11266

import java.io.*;
import java.util.*;

public class Main {

    static int V, E;
    static ArrayList<Integer>[] tree;
    static Set<Integer> answer;
    static int[] order;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        tree = new ArrayList[V+1];
        for (int i = 1; i <= V; i++)
            tree[i] = new ArrayList<>();

        E = Integer.parseInt(st.nextToken());
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            tree[a].add(b);
            tree[b].add(a);
        }

        order = new int[V+1];
        answer = new HashSet();
        for (int i = 1; i <= V; i++)
            if (order[i]==0)
                dfs(i, true, 0);

        ArrayList<Integer> tmp = new ArrayList<>(answer);
        Collections.sort(tmp);
        bw.write(tmp.size()+"\n");
        for (int item : tmp)
            bw.write(item+" ");

        bw.flush();
        bw.close();
        br.close();
    }
    static int cnt=1;
    static int dfs(int id, boolean isRoot, int parent){
        order[id] = cnt++;
        int ret = order[id];
        int child = 0;
        for (int now : tree[id]) {
            if (now == parent) continue;
            
            if (order[now]==0){
                child++;
                int low = dfs(now, false, id);
                if (!isRoot && low >= order[id])
                    answer.add(id);
                ret = Math.min(ret, low);
            } else
                ret = Math.min(ret, order[now]);
        }
        if (isRoot && child>=2)
            answer.add(id);
        return ret;
    }
}

단순union이 아니라 dfs를 이용해서 그래프에서 사이클이 없는지 탐색하는 부분이 잘 이해가 안된다..

조금 더 꼼꼼히 뜯어볼 필요가 있을것같다.