[SWEA] 4727. 견우와 직녀 (18.8.6 수정) - Java

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWSHOpR6f_sDFARw 

SW Expert Academy

---

1. 문제 요약

N*N크기 지도에서 견우(0,0)가 직녀(N-1,N-1)에게 갈 수 있는 최소시간을 구하라.

지도의 값이

0이면 절벽, 1이면 길, 1보다 크면 다리의 쉬는시간 주기이다. 다리는 쉬는시간이 끝나면 건널 수 있다.

딱 한 번만 다리 하나를 추가로 더 생성할 수 있다. 이 다리의 쉬는시간 주기는 M이다.

 

2. 풀이

처음엔 DFS로 접근하였다. 새로운 다리를 놓아보고 직녀를 만나러 가는데 아니면 다시 돌아와서 다른 자리에 다리를 놓아보고 할 생각으로 백트래킹이 적절하다고 생각했다.

근데 이렇게 하니까 시간초과가 뜨더라. 20개 중에 12개 맞았다.

최단 시간을 구하는 문제이므로 DFS보다는 BFS가 적절하다.

하지만 다리를 놓아보는 작업은 백트래킹이 아닌가? -> 처음에 입력받을 때 0인 좌표를 저장해뒀다가

for문을 돌려서 좌표마다 다리를 놓았다고 치고 bfs를 돌리는 것이다.

이렇게 하니 통과했다.

다리를 놓았다가 치웠다가면 백트래킹인데 최단거리면 BFS?? 이런 틀에 갇힌 생각 때문에 꽤나 헤맸다.

 

그리고 새로운 다리는 겹치는 부분에 둘 수 없다는 조건이 있는데,

이 조건 때문에 4방탐색을 한번 더 해주면 그건 낚인 것이다.

어차피 visited true면 방문을 안할테고, map[ny][nx]==0이면 continue할것이니까 무시해도 되는 조건이다.

 

3. 코드

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

public class SW_4727_견우와직녀 {

	static int N,M, ans;
	static int[][] map;
	static int[] dy= {-1,1,0,0};
	static int[] dx= {0,0,-1,1};
	
	static List<Pos> blank;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		
		for (int tc=1; tc<=T; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			map = new int[N][N];
			blank = new ArrayList<> ();
			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] == 0) {
						blank.add(new Pos(i, j)); //절벽
					}
				}
			}//입력 끝
			
			ans = Integer.MAX_VALUE;
			for (Pos node : blank) {
				map[node.y][node.x] = M;
				int res = bfs();
				map[node.y][node.x] = 0;
				

				//System.out.println(node.y+", "+node.x+" res:" + res);
				
				if (res==0) continue;
				else ans = Math.min(ans, res);
			}
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	static int bfs() {
		int res = 0;
		Queue<Pos> queue = new ArrayDeque<> ();
		boolean[][] visited = new boolean[N][N];
		
		queue.offer(new Pos(0,0,0));
		visited[0][0] = true;
		
		while (!queue.isEmpty()) {
			Pos cur = queue.poll();
			int y=cur.y;
			int x=cur.x;
			int sec=cur.sec;
			
			if (y==N-1 && x==N-1) {
				res = sec;
				break;
			}
			
			for (int d=0; d<4; d++) {
				int ny = y+dy[d];
				int nx = x+dx[d];
				if (ny<0 || ny>=N || nx<0||nx>=N || visited[ny][nx] == true) continue;
				
				if (map[ny][nx] == 0) continue;
				
				else if (map[ny][nx] == 1) {
					queue.offer(new Pos(ny,nx,sec+1));
					visited[ny][nx] = true;
				} 
				
				else if (map[ny][nx] > 1) {
					if (map[y][x] == 1) {
						if ((sec+1) % map[ny][nx] == 0) {
							queue.offer(new Pos(ny,nx,sec+1));
							visited[ny][nx] = true;
						} else {
							queue.offer(new Pos(y,x,sec+1));
						}
					}
				}
			}
		}
		return res;
	}
	
	static class Pos {
		int y,x,sec;
		boolean used;
		Pos(int y, int x) {
			this.y = y;
			this.x = x;
		}
		Pos(int y, int x, int sec) {
			this.y = y;
			this.x = x;
			this.sec = sec;
		}
	}
}

4. 사담

잘하고있는거였으면 좋겠다 언제쯤 실력이 늘까