[이코테] 경쟁적 전염

문제 링크 : https://www.acmicpc.net/problem/18405

 

---

package codingTest;

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

public class competeInf {
    private static void bfs(int N, int K, int graph[][], int S, int X, int Y) {
        for (int i = 0; i < S; i++) {
            for (int j = 1; j <= K; j++) {
                bfsGraph(N,j, graph);
                if(graph[i][j]!=0) break;
            }
        }

//        System.out.println(graph[X][Y]);
    }

    private static void bfsGraph (int N, int num, int graph[][]) {
        Queue<Integer> q = new LinkedList<>();

        int dx[] = {0,-1,0,1};
        int dy[] = {1,0,-1,0};

        int ix=0;
        int iy=0;

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if(graph[i][j]==num) {
                    q.offer(num);
                    ix = i;
                    iy = j;
                }
            }
        }

        // 상하좌우 값 찾기
        for (int i = 0; i < 4; i++) {
            int v = q.poll();
            int nx = ix + dx[i];
            int ny = iy + dy[i];
            if(nx<1 || ny<1 || nx> N || ny > N) {
                continue;
            }
            graph[nx][ny] = v;
        }

    }

    public static void main(String[] args) {
        // N*N
        int N = 3;
        // 1부터 K까지
        int K = 3;
        // 담겨있는 graph
        int graph[][] = {{}, {1, 0, 2}, {0, 0, 0,}, {3, 0, 0}};
        // 시간
        int S = 3;
        //(x,y) 좌표
        int X = 3;
        int Y = 2;
        bfs(N, K, graph, S, X, Y);
    }
}

 

일단 이렇게 처음을 짰고 처음 결과는 다음과 같다.

N*N에서 하나씩 더하기 싫어서 1부터 시작했는데 생각하지 못한 부분에서 오류가 난 거 같다.

쪼개서 계속 하니까 헷갈리기도 하고 그래서 구조를 다시 생각했다.

-> main 부분에 S초 만큼 for 문을 돌리고 K만큼 이중 for 문을 돌린 후 1부터 K 마다 bfs를 하면 어떨까 생각해봤다.

 

public class competeInf {
    private static void bfs(int n, int k, int graph[][], int x, int y) {
        int ix=0; int iy = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(graph[i][j]==k) {
                    ix = i;
                    iy = y;
                }
            }
        }

        int dx[] = {0,-1,0,1};
        int dy[] = {1,0,-1,0};

        for (int i = 0; i < 4; i++) {
            int nx = ix+dx[i];
            int ny = iy+dy[i];
            if(nx<1||ny<1||nx>n|| ny>n) {
                continue;
            }
            graph[nx][ny] = k;
        }

    }

    public static void main(String[] args) {
        // N*N
        int N = 3;
        // 1부터 K까지
        int K = 3;
        // 담겨있는 graph
        int graph[][] = {{}, {1, 0, 2}, {0, 0, 0}, {3, 0, 0}};
        // 시간
        int S = 3;
        //(x,y) 좌표
        int X = 3;
        int Y = 2;

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

                bfs(N, j+1, graph, X, Y);

            }
        }

        System.out.println(graph[X][Y]);

    }
}