[코드트리/INTERMEDIATE LOW] 우리는 하나 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

💡  풀이 방식

• 백트래킹 + BFS

사용 자료구조
[백트래킹용]
- 도시 위치와 인덱스 저장할 int형 2차원 배열 ⇨ int[][] cities = new int[n*n + 1][2];
- 뽑은 도시 저장할 int형 리스트

[BFS용]
- dx/dy 배열
- 방문 표시 배열

- 최댓값

 

• 도시 정보를 입력받을 때 해당 도시의 행,열 값과 인덱스를 도시 정보 배열 cities에 저장한다.
• 백트래킹을 통해 도시 정보 배열을 돌며 이 중 도시 k개를 뽑는다.
  • 만약 k개를 뽑지 않았다면, 해당 인덱스의 도시를 뽑고 다음 인덱스로 넘어간다.
  • k개를 뽑았다면, 뽑은 k개의 도시에 대해 bfs 탐색을 하며 갈 수 있는 도시에 방문 표시를 한다.
    1. 방문 표시 배열의 값을 모두 미방문(=false) 상태로 초기화한다.
    2. 뽑은 k개 도시들을 돌며 bfs 탐색을 수행한다. (이미 방문 표시된 도시라면 굳이 또 bfs를 진행하지 않아도 된다. 그러면 수행시간 2배 가량 줄이기 가능!)
    3. 갈 수 있는 칸 수(= 방문 표시 배열에서 방문 표시한 칸의 수)를 구하고, 이를 최댓값과 비교해 더 큰 값으로 최댓값을 갱신한다.

 

 

 

💥 유의사항

- 방문 배열의 초기화 위치

- 백트래킹 종료 조건

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int n,k,u,d;
    static int[][] map;
 
    // dfs용
    static int[][] cities;  // 도시의 위치와 인덱스 저장용 배열
    static List<Integer> list = new ArrayList<>();  // 뽑은 도시 저장할 리스트
 
    // bfs용
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static boolean[][] visited;
 
    static int max = 1;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        n = Integer.parseInt(st.nextToken());   // 격자 크기
        k = Integer.parseInt(st.nextToken());   // 고를 도시 수
        u = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
 
        map = new int[n+1][n+1];
        cities = new int[n*n + 1][2];
 
        int idx = 1;
        for(int i = 1 ; i <= n ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 1 ; j <= n ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
 
                cities[idx][0] = i;
                cities[idx][1] = j;
 
                idx++;
            }
        }
 
        visited = new boolean[n+1][n+1];
        comb(1, 0);
 
        System.out.println(max);
    }
 
    // 도시 K개 골라서 갈 수 있는 서로 다른 도시 수 중 최댓값 구하기
    private static void comb(int idx, int depth) {
        if(depth == k) {    
            // 1. 방문 배열 초기화하기
            initialize();
 
            // 2. 뽑은 도시들을 돌며 BFS 탐색 수행
            for(int i = 0 ; i < list.size() ; i++) {
                int num = list.get(i);
                int x = cities[num][0];
                int y = cities[num][1];
 
                if(visited[x][y])   continue;   // 이 한 줄이면 수행시간 2배 정도 줄어듦
                bfs(x, y);
            }
 
            // 3. 갈 수 있는 서로 다른 도시 수 구하고 최댓값과 비교해 갱신하기
            max = Math.max(max, getCnt());            
            return;
        }
 
        // K개 뽑지 않았다면, 해당 도시 뽑기
        for(int i = idx ; i < cities.length ; i++) {
            list.add(i);
            comb(i + 1, depth + 1);
            list.remove(list.size() - 1);
        }
    }
 
    private static void bfs(int x, int y) {
        visited[x][y] = true;
 
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y});
 
        while(!q.isEmpty()) {
            int[] now = q.poll();
 
            for(int dir = 0 ; dir < 4 ; dir++) {
                int nx = now[0] + dx[dir];
                int ny = now[1] + dy[dir];
 
                // 격자 범위 내 있고, 방문한 적 없고, 차이가 u 이상 d 이하인 도시로 이동
                if(!inRange(nx,ny) || visited[nx][ny])  continue;
 
                int diff = Math.abs(map[nx][ny] - map[now[0]][now[1]]);
                if(u <= diff && diff <= d) {
                    visited[nx][ny] = true;
                    q.add(new int[]{nx, ny});
                }
            }
        }
    }
 
    // 갈 수 있는 서로 다른 도시 수 구하는 함수
    private static int getCnt() {
        int cnt = 0;
 
        for(int i = 1 ; i <= n ; i++) {
            for(int j = 1 ; j <= n ; j++) {
                if(visited[i][j])
                    cnt++;
            }
        }
        return cnt;
    }
 
    // 방문 배열 초기화 함수
    private static void initialize() {
        for(int i = 1 ; i <= n ; i++) {
            for(int j = 1 ; j <= n ; j++) {
                visited[i][j] = false;
            }
        }
    }
 
    private static boolean inRange(int x, int y) {
        return (1 <= x && x <= n && 1 <= y && y <= n);
    }    
}

 

 

 

➕ 다른 풀이 방식

N개 중에 M개 뽑고자 할 때 이렇게 작성해도 된다.

private static void comb(int idx, int depth) {
    if(depth == k) {
        initialize();

        for(int i = 0 ; i < list.size() ; i++) {
            int num = list.get(i);
            int x = cities[num][0];
            int y = cities[num][1];

            if(visited[x][y])   continue;
            bfs(x, y);
        }

        max = Math.max(max, getCnt());            
        return;
    }

    if(idx == n*n)
        return;

    // 해당 인덱스의 도시를 뽑았을 때
    list.add(idx);
    comb(idx + 1, depth + 1);
    list.remove(list.size() - 1);

    // 해당 인덱스의 도시를 뽑지 않았을 때
    comb(idx + 1, depth);
}

 

---

💦 어려웠던 점

다 맞게 작성했었는데 4방향 탐색할 때 변수 d를 썼는데 이 문제에서 전역변수 d를 사용해서 제대로 bfs탐색이 안 되었던 것이다,,,,,,,,,,,,ㅠ

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리 .. ❤