코테 | 그래프 섹션 - 다익스트라, 위상정렬 문풀

🟩 4번. 방향 바꾸기

• 4방향으로 갈수 있기 때문에 cost[][] 2차원 배열 생성하여 최대한 방향 적게 바꾸면서 갈 수 있는 방식 고안
• PriorityQueue에 좌표 담아가면서 가중치 적은 거 우선 정렬
• int dir 변수가 순서대로 dx, dy 순회하면서

1. 방향 안바꾼 상태로 더 적은 값 갱신 가능하면 갱신
2. 방향 바꾼 상태로 더 적은 값 갱신 가능하면 갱신

• 정답 출력

package to_0822_6;
//다익스트라 - 방향 바꾸기 RE 풀이 
import java.util.*;
class Solution {
	static int N, M;
	static int[][] cost;
	static PriorityQueue<int[]> pQ;
	//4방향 
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};	
	
	//솔루션 함수 
    public int solution(int[][] board) {
    	
    	N = board.length;
    	M = board[0].length;
    	
    	cost = new int[N][M];
    	//가중치 오름차순 즉 작은 가중치 우선 정렬 
    	pQ = new PriorityQueue<>((a, b) -> a[2]-b[2]);
    	//무한대로 비용 초기화
    	for(int i=0 ; i<N; i++) Arrays.fill(cost[i], Integer.MAX_VALUE);
    	
    	//시작점 세팅
    	cost[0][0] = 0;
    	pQ.add(new int[] {0,0, 0});
    	
    	while(!pQ.isEmpty()) {
    		int[] cur = pQ.poll();
    		int dir = board[cur[0]][cur[1]] -1;//이게 방향 좌표지칭
    		//현재 뽑은 가중치가 기존 비용보다도 클 경우에는 탐색 안하고 넘어감 
    		if(cur[2] > cost[cur[0]][cur[1]]) continue;
    		
    		for(int k=0; k<4; k++) {
    			int nx = cur[0] + dx[k];
    			int ny= cur[1] + dy[k];
    			if(nx <0 || ny<0 ||nx>=N || ny >=M) continue;
    			//방향이 같으면서 현재 비용이 더 작을 경우 갠신 
    			if(dir == k && cur[2] < cost[nx][ny]) {
    				cost[nx][ny] = cur[2];
    				pQ.offer(new int[] {nx, ny, cur[2]});
    			}else if(dir != k && cur[2] +1 <cost[nx][ny]) {
    				cost[nx][ny] = cur[2]+1;
    				pQ.offer(new int[] {nx, ny, cur[2]+1});
    			}
    		}
    	}
    	return cost[N-1][M-1];
    }

	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(new int[][]{{3, 1, 3}, {1, 4, 2}, {4, 2, 3}}));
		System.out.println(T.solution(new int[][]{{3, 2, 1, 3}, {1, 1, 4, 2}, {3, 4, 2, 1}, {1, 2, 2, 4}}));
		System.out.println(T.solution(new int[][]{{3, 2, 1, 3, 1, 2}, {2, 1, 1, 1, 4, 2}, {2, 2, 2, 1, 2, 2}, {1, 3, 3, 4, 4, 4}, {1, 2, 2, 3, 3, 4}}));
		System.out.println(T.solution(new int[][]{{3, 2, 1, 3, 1, 2, 2, 2}, {2, 1, 1, 1, 4, 2, 1, 1}, {2, 2, 2, 1, 2, 2, 3, 4}, {1, 3, 3, 4, 4, 4, 3, 1}, {1, 2, 2, 3, 3, 4, 3, 4}, {1, 2, 2, 3, 3, 1, 1, 1}}));
		System.out.println(T.solution(new int[][]{{1, 2, 3, 2, 1, 3, 1, 2, 2, 2}, {1, 2, 2, 1, 1, 1, 4, 2, 1, 1}, {3, 2, 2, 2, 2, 1, 2, 2, 3, 4}, {3, 3, 1, 3, 3, 4, 4, 4, 3, 1}, {1, 1, 1, 2, 2, 3, 3, 4, 3, 4}, {1, 1, 1, 2, 2, 3, 3, 1, 1, 1}}));
	}
}

---

🟩 5번. 공 굴리기

• 벽 만나기 전까지는 수직 or 수평으로만 쭉 이동하다가 벽 만나야 멈춘다.
• 예를 들어, 벽을 못만난 상태로 도착 지점에 가도 그냥 지나치기 때문에 도착 못하는 게 되는 것
• 그냥 지나치면 안되고 도착 지점에서 벽을 만나 멈춰야 그때까지 이동한 값들 누적하여 턴

풀이

• 벽을 만나기 전까지 while문으로 그 길이 ++ 처리한다.
• while 탈출 시 직전 지점과 len으로 되돌리고, 해당 값의 기존 cost 비용보다 더 작은 값으로 갱신 가능하면 len으로 갱신처리

package to_0822_C;
import java.util.*;
class Solution {
	public int solution(int[][] board, int[] s, int[] e){
		int n = board.length;
		int m = board[0].length;
		int[][] cost = new int[n][m];
		for(int i = 0; i < n; i++) Arrays.fill(cost[i], Integer.MAX_VALUE);
		PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
    	pq.add(new int[]{s[0], s[1], 0});
    	cost[s[0]][s[1]] = 0;
        	
    	while(!pq.isEmpty()) {
           int[] cur = pq.poll();
           if(cur[2] > cost[cur[0]][cur[1]]) continue;
           //방향을 4방향으로 가긴 할거임 
           for(int[] dir : new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}){
            	int nx = cur[0];
            	int ny = cur[1];
            	int len = cur[2]; //초기화
            	//while문 돌면서 : 벽인 1이 나오기 전까지 값이 0이면서 범위 벗어나지 않는 동안 갈 수 있는 매끄러운 길이 len++ 처리하며 이동 
            	while(nx>= 0 && nx < n&& ny >= 0 && ny < m && board[nx][ny] == 0){
                	nx += dir[0]; //이동
               	 	ny += dir[1];//이동 
                	len ++;//길이++
            	}
            	//1 만나거나 범위 벗어나서 탈출 : 벽 만남
            	//1인 벽을 만나서 1개씩 직전으로 빼줌 
            	nx -= dir[0];
            	ny -= dir[1];
            	len --;
            	
            	//이제 이 지점까지의 len길이가 기존의 cost 비용보다 작을 경우 값 갱신처리 
            	if(cost[nx][ny] > len){
					 cost[nx][ny] = len;
                	 pq.add(new int[]{nx, ny, len});
           	    }
       	    }
    	}
    	//여전히 그대로 max값일 경우 -1
		if(cost[e[0]][e[1]] == Integer.MAX_VALUE) return -1;
	    //아닌 경우 비용 반환
		else return cost[e[0]][e[1]];
   	}
	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(new int[][]{{0, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 0}, {1, 0, 1, 1, 1, 0}, {1, 0, 0, 0, 0, 0}}, new int[]{1, 0}, new int[]{4, 5}));
		System.out.println(T.solution(new int[][]{{0, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 0}, {1, 0, 1, 1, 1, 0}, {1, 0, 0, 0, 0, 0}}, new int[]{0, 0}, new int[]{4, 2}));
		System.out.println(T.solution(new int[][]{{1, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 0}, {1, 1, 0, 1, 1}, {0, 0, 0, 0, 0}}, new int[]{0, 3}, new int[]{4, 2}));
		System.out.println(T.solution(new int[][]{{0, 1, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0}, {0, 1, 1, 0, 1, 1}, {0, 0, 0, 0, 0, 0}}, new int[]{0, 0}, new int[]{4, 5}));
		System.out.println(T.solution(new int[][]{{0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0}}, new int[]{0, 0}, new int[]{4, 3}));
	}
}

---

🟩 6번. 교육 과정 | 위상 정렬

• 전형적인 위상 정렬 문제이다.
• 각 과목들은 정점이 되고, course 배열에 담긴 선수강 순서가 간선이 된다.
• ‘답이 여러 개면 아무거나 반환’ 하라는 것
• = 위상 정렬 결과값이 항상 유일하지 않기 때문

⚫ 위상 정렬

• 사이클 X 방향 그래프에서 노드 순서 찾는 알고리즘

[위상 정렬 풀이]

• 진입차수 0인 정점 Q에 담기
• Q에서 뽑은 값을 결과에 추가하고, 뽑은 정점이 가리키는 노드들의 진입차수 -1 처리를 한다.
• 만약 뺀 진입차수가 0인 정점 생기면 다시 Q에 담고
• 이 과정을 큐가 빈 상태가 될 때까지 반복하면 된다.

풀이

package to_0823_4;
import java.util.*;
//교육 과정- 위상정렬 문풀
class Solution {
	public String[] solution(String[] subjects, String[] course){
		
		int n= subjects.length;
		//번호 마킹 <key, 값>
		HashMap<String, Integer> map = new HashMap<>();
		for(int i=0; i<n; i++) {
			map.put(subjects[i], i);//번호 
		}
		//그래프 생성 
		ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
		for(int i=0; i<n; i++) graph.add(new ArrayList<>());
		
		int[] indegree = new int[n];
		
		//데이터 삽입
		for(int i=0; i<course.length; i++) {
			int a = map.get(course[i].split(" ")[0]);
			int b = map.get(course[i].split(" ")[1]);
			
			//방향 그래프 b 듣고 a 들어야 한다.
			graph.get(b).add(a);
			//진입차수 처리
			indegree[a]++;
		}
		
		//위상정렬 시작 
		Queue<Integer> Q= new LinkedList<>();
		//정답 세팅ㅎ 번호
		ArrayList<Integer> arr = new ArrayList<>();
		String[] answer = new String[n];//레알 정답용 
		
		for(int i=0; i<n; i++) {
			if(indegree[i]==0) {
				Q.offer(i);
			}
		}
	
		while(!Q.isEmpty()) {
			int cur = Q.poll();//진입차수 0인애 하나 뽑음
			arr.add(cur);//번호만 담기 
			for(int nx : graph.get(cur)) {
				//뽑은 정점이 가리키는 정점들의 진입차수를 -처리
				indegree[nx]--;
				if(indegree[nx] == 0) {
					Q.add(nx);
				}
			}
		}
		
		//정답 세팅 
		for(int i=0; i<n; i++) {
			//arr에 담은 과목 번호 순서대로 -> subject의 각 과목 번호에 접근하여 그 번호로 answer[i]를 세팅
			answer[i] = subjects[arr.get(i)];
		}

		return answer;
    }
		
	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(Arrays.toString(T.solution(new String[]{"english", "math", "physics", "art", "music"}, new String[]{"art math", "physics art", "art music", "physics math", "english physics"})));

		//System.out.println(T.solution(new String[]{"english", "math", "physics", "art", "music"}, new String[]{"art math", "physics art", "art music", "physics math", "english physics"}));
		//System.out.println(T.solution(new String[]{"art", "economics", "history", "chemistry"}, new String[]{"chemistry history", "economics history", "art economics"})[0]);
		//System.out.println(T.solution(new String[]{"math", "science", "music", "biology"}, new String[]{"science music", "math music", "math science", "biology math"}));
	}
}