[코드트리/BFS] 우리는 하나

문제

https://www.codetree.ai/trails/complete/curated-cards/test-we-are-the-one/description?page=1&page_size=20

Code Tree | Learning to Code with Confidence

 

해결방법

처음 문제를 읽었을땐 인접한 도시간의 이동, U 이상 D이하인 경우 이 부분에 대해 이해가 잘 되지 않았다. 인접한 도시간의 이동이 연쇄적으로 일어나는 일인지 설명이 모호했다고 생각한다. 그리고 U이상 D이하의 의미가 처음 선택한 도시와 이동하려는 도시와의 비교인지, 현재 도시와 다음 도시간의 비교인지 헷갈렸다. 테스트케이스를 통해 분석한 결과 문제에서 요구하는 조건은 다음과 같았다.

• 일반적인 BFS문제처럼 연쇄적으로 이동 가능
• 현재 도시와 다음 도시간 높이 비교

 

해당 문제를 해결하려면 K개의 도시를 고르는 조합 경우의수와 BFS로 인접 도시의 수를 계산하는 로직을 작성해야한다. 조합 경우의 수를 구현하는 방법은 재귀 함수를 사용하여 구현하였다. BFS로 인접도시의 수를 계산하는 로직은 일반적인 BFS구현 방법에서 높이 비교를 통해 이동 가능한지 판별하는 조건문을 추가하여 쉽게 구현이 가능하다.

실수했던 내용

재귀함수로 경우의 수를 구현할때 아래의 코드처럼 작성했었다.

    static void comb(int x, int y, int cCnt){
        if(cCnt == K){
            // 연산 메소드
            return;
        }

        for(int i = x + 1; i < N; i++){
            for(int j = y + 1; j < N; j++){
                cities[cCnt] = new Position(j, i); 	// 요소 선택
                comb(i, j, cCnt + 1);	// 재귀
            }
        }
    }

반복자의 시작에 +1을 했던 이유는 이미 방문한 위치를 또 반복하지 않기 위함이었으나, 2중 반복문에서는 inner loop에서 매번 +1씩 일어나기때문에 모든 경우를 탐색하지 못했다. 이를 해결하기 위해 이번 문제에서는 +1을 지우고 중복을 허용하도록 임시방편으로 구현하였다. 이런 선택을 한 이유는 중복으로 조합을 선택하여도 시간복잡도가 많이 남는 문제이므로 시간초과가 발생하지 않고, 최대값을 찾는 문제이기때문에 답에 영향을 주지 않기 때문이다. 그러나 앞으로 조합의 수를 구현해야하는 문제에서는 해당 방법으로 하는 경우에는 문제가 발생할 수 있기때문에 조합 구현하는방법을 다시 공부 해야할 것 같다.

 

소스코드

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

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

public class Main {
    static int N, K, U, D;
    static int[][] map;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int answer = 0;
    static Position[] cities;
    public static void main(String[] args) throws IOException{
        // Please write your code here.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] first = br.readLine().split(" ");
        N = Integer.parseInt(first[0]);
        K = Integer.parseInt(first[1]);
        U = Integer.parseInt(first[2]);
        D = Integer.parseInt(first[3]);
        map = new int[N][N];
        cities = new Position[K];
        for(int i = 0; i < N; i++){
            String[] line = br.readLine().split(" ");
            for(int j = 0; j < N; j++){
                map[i][j] = Integer.parseInt(line[j]);
            }
        }

        comb(0, 0, 0);

        System.out.println(answer);
    }

    static void comb(int x, int y, int cCnt){
        if(cCnt == K){
            answer = Math.max(bfs(), answer);
            return;
        }

        for(int i = x; i < N; i++){
            for(int j = y; j < N; j++){
                cities[cCnt] = new Position(j, i);
                comb(i, j, cCnt + 1);
            }
        }
    }

    static int bfs(){
        int cnt = 0;
        int[][] visited = new int[N][N];
        for(int i = 0; i < K; i++){
            Queue<Position> queue = new LinkedList<>();

            if(visited[cities[i].y][cities[i].x] == 1)
                continue;
            queue.add(cities[i]);
            visited[cities[i].y][cities[i].x] = 1;
            while(!queue.isEmpty()){
                Position now = queue.poll();
                cnt++;
                for(int j = 0; j < 4; j++){
                    Position next = new Position(now.x + dx[j], now.y + dy[j]);

                    if(next.x < 0 || next.x >= N || next.y < 0 || next.y >= N)
                        continue;
                    if(visited[next.y][next.x] == 1)
                        continue;
                    if(!canGo(now, next))
                        continue;
                    
                    visited[next.y][next.x] = 1;
                    queue.add(next);
                }
            }
        }

        return cnt;
    }

    static boolean canGo(Position p1, Position p2){
        int diff = Math.abs(map[p1.y][p1.x] - map[p2.y][p2.x]);
        return diff >= U && diff <= D;
    }
}