[SWEA] 1949 등산로조성 (BFS로 풀어보기)

1. 문제

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

SW Expert Academy

2. 접근방법

dfs로 풀면 정말정말 간단하게 풀어 낼 수 있지만

뜬금없는 바람이 불어서 bfs로 풀어내보자 하고 무수한 삽질 끝에 풀어냈다.

 

꽤나 재밌었다.

 

먼저 맵 입력을 받을 때 최대값들의 위치를 list에 저장하고

입력이 끝난후 bfs에 쓰일 que에 모두 집어 넣는다.

여기서 특이한 부분이 2가지 있는데 node를 보면

 

하나는 현재 위치의 숫자 num 즉 map[i][j]값을 굳이 저장해서 들고 다닌다는 점과

자신의 visit배열을 아예 들고 다니는것이다.

 

num의 경우 map에서 안꺼내 쓰는 이유는

K의 크기만큼 공사로 땅을 깍아낼 수 있다라는 조건 때문에

bfs의 특성상 여러 가지가 함께쓰는 map을 공사시켜버리면 큰일나기 때문에

공사 했더라도 그 값을 map에 변화안시키고 다닐수 있도록 하기 위함이다.

use는 한번의 공사기회를 쓴 가지인지 아닌지 검사하는 것

 

그리고 어차피 숫자가 작아지는대로 찾아가면 되니 visit이 필요없지 않나?라고 생각할 수 있는데

이렇게 돌아와서 자기 원래 경로를 공사해버리는 경우가 생길 수 있으니 visit처리를 해주어야 한다.

 

그런데 bfs는 여러 가지가 동시에 뻗쳐 나가다보니

각각의 가지가 스스로 지나온 길을 체크할 수 있어야 하는데 하나의 visit으로는 결코 불가능하다..

 

그래서 각 가지가 모두 자신의 길을 체크하고 있는 visit배열을 들고 다니는 방법을 선택했다.

 

자 이제 시뮬에서 시키는데로 본인의 위치에서 더 낮은 길만 찾아가면서 만약 공사를 하고 갈 수 있다면

한번의 기회안에서 공사도 해보며 가장 긴 등산로를 찾아내면 된다.

 

 

3. 자바 코드

package D3;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class P1949등산로조성 {
	static class node{
		int x;
		int y;
		int cnt;
		int num;
		boolean use;
		boolean visit[][]; //이렇게 까지 해야하나 자괴감이 든다.
		public node(int x, int y, int cnt, int num, boolean use,boolean visit[][]) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
			this.num = num;
			this.use = use;
			this.visit = visit;
		}
		
	}
	
	
	public static void main(String args[]) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int T;
		T = Integer.parseInt(st.nextToken());
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			int map[][] = new int[N][N];
			int maxnum = 0;
			List<Point> maxfriend = new ArrayList<Point>();
			for(int i = 0 ; i < N ; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j = 0 ; j < N ; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if(map[i][j] > maxnum) {
						maxfriend.clear();
						maxfriend.add(new Point(i,j));
						maxnum = map[i][j];
					}else if(map[i][j] == maxnum) {
						maxfriend.add(new Point(i,j));
					}
				}
			}
			Queue<node> que = new LinkedList<node>();
			
			for(int i = 0 ; i < maxfriend.size() ; i++) {
				Point p = maxfriend.get(i);
				boolean visit[][] = new boolean[N][N]; 
				visit[p.x][p.y] = true;
				que.offer(new node(p.x, p.y, 1, maxnum, false,visit));
			}
			
			
			int max = 0;
			int dr[] = {-1,1,0,0};
			int dc[] = {0,0,1,-1};
			while(!que.isEmpty()) {
				node now = que.poll();
				max = Math.max(max, now.cnt);
				for(int d = 0 ; d < 4 ; d++) {
					
					int row = now.x + dr[d];
					int col = now.y + dc[d];
					if(row < 0 || col < 0 || row >= N || col >= N)
						continue;
					if(now.visit[row][col])
						continue;
					
					boolean[][] myvisit = new boolean[N][N]; 
					for(int i = 0 ; i < N ; i++) 
						myvisit[i] = now.visit[i].clone();
					myvisit[row][col] = true;
					
					if(map[row][col] >= now.num ) {
						if( now.use|| map[row][col] - K >= now.num)
							continue;
						que.offer(new node(row, col, now.cnt+1,now.num-1 ,true,myvisit));
						continue;
					}
					que.offer(new node(row,col,now.cnt+1,map[row][col],now.use,myvisit));
				}
			}
			System.out.printf("#%d %d\n", tc,max);
		}
	}

}

4. 마치며

사실 dfs로 풀면 하나의 경로가 끝을 만날때까지 가기 때문에 visit처리를 하기가 간편해지는데

 

bfs로 풀어보고 싶어서 이런 이상한짓? 까지 해보았다.

 

나름 bfs로 어떻게 해결이 가능할까 고민을 하면서 재밌었다.