Algorithm/SWEA

AD 230120 오답노트 중,.

Bonita SY 2023. 1. 20. 13:37
728x90
반응형

첫번째 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class AD230120 {
	public static final int X = 0;
	public static final int Y = 1;
	public static final int[] EWSN_X = { 1, -1, 0, 0 };
	public static final int[] EWSN_Y = { 0, 0, 1, -1 };
	
	public static int N;
	public static int M;
	public static char[][] map;
	public static boolean[][] wall;
	public static boolean[][] visited;
	
	public static int[] red_position;
	public static int[] blue_position;
	
	public static int red_weight;
	public static int blue_weight;
	public static int dest_weight;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		for (int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			map = new char[N+1][M+1];
			wall = new boolean[N+1][M+1];
			visited = new boolean[N+1][M+1];
			
			red_position = new int[2];
			blue_position = new int[2];
			
			red_weight = Integer.MAX_VALUE;
			blue_weight = Integer.MAX_VALUE;
			dest_weight = Integer.MAX_VALUE;
			
			int answer = 0;
			
			for (int n=0; n<N; n++) {
				String line = br.readLine();
				for (int m=0; m<M; m++) {
					char elem = line.charAt(m);
					map[n+1][m+1] = elem;

					if (elem == 'X') {
						wall[n+1][m+1] = true;
						visited[n+1][m+1] = true;
					} else if (elem == 'R') {
						red_position[X] = n+1;
						red_position[Y] = m+1;
					} else if (elem == 'B') {
						blue_position[X] = n+1;
						blue_position[Y] = m+1;
					}
				}
			}
			
			// 빨간 풍선을 찾아라
			findRed(1, 1, 0);
			if (red_weight == Integer.MAX_VALUE) {
				System.out.printf("#%d -1\n", tc);
				continue;
			}
			answer += red_weight;
			
			// 빨간 풍선 버리고 파란 풍선을 찾아라
			wasteRedFindBlue(red_position[X], red_position[Y], 0);
			if (blue_weight == Integer.MAX_VALUE) {
				System.out.printf("#%d -1\n", tc);
				continue;
			}
			answer += blue_weight;
			
			// 종점 가기
			goDestination(blue_position[X], blue_position[Y], 0);
			if (dest_weight == Integer.MAX_VALUE) {
				System.out.printf("#%d -1\n", tc);
				continue;
			}
			answer += dest_weight;
			System.out.printf("#%d %d\n", tc, answer);
		}
	}
	
	public static void goDestination(int x, int y, int weight) {
		if (x < 1 || x > N || 
				y < 1 || y > M || 
				visited[x][y] || 
				dest_weight <= weight) {
			return;
		}
		
		if (x == N && y == M) {
			if (dest_weight > weight) {
				dest_weight = weight;
			}
			return;
		}
		
		visited[x][y] = true;
		for (int i=0; i<4; i++) {
			int new_x = x + EWSN_X[i];
			int new_y = y + EWSN_Y[i];
			
			goDestination(new_x, new_y, weight+1);
		}
		visited[x][y] = false;
	}
	
	public static void findRed(int x, int y, int weight) {
		if (x < 1 || x > N || 
				y < 1 || y > M || 
				visited[x][y] || 
				red_weight <= weight) {
			return;
		}
		
		if (map[x][y] == 'R') {
			if (red_weight > weight) {
				red_weight = weight;
			}
			return;
		}
		
		visited[x][y] = true;
		for (int i=0; i<4; i++) {
			int new_x = x + EWSN_X[i];
			int new_y = y + EWSN_Y[i];
			
			findRed(new_x, new_y, weight+1);
		}
		visited[x][y] = false;
	}
	
	public static void wasteRedFindBlue(int x, int y, int weight) {
		if (x < 1 || x > N || 
				y < 1 || y > M) {
			int cur_x = x;
			int cur_y = y;
			
			if (x < 1) {
				cur_x = 1;
			} else if (x > N) {
				cur_x = N;
			}
			
			if (y < 1) {
				cur_y = 1;
			} else if(y > M) {
				cur_y = M;
			}
			
			findBlue(cur_x, cur_y, weight-1);
			return;
		}
		
		if (visited[x][y]) {
			return;
		}
		
		visited[x][y] = true;
		for (int i=0; i<4; i++) {
			int new_x = x + EWSN_X[i];
			int new_y = y + EWSN_Y[i];
			
			wasteRedFindBlue(new_x, new_y, weight+1);
		}
		visited[x][y] = false;
	}
	
	public static void findBlue(int x, int y, int weight) {
		if (x < 1 || x > N || 
				y < 1 || y > M || 
				wall[x][y] || 
				blue_weight <= weight) {
			return;
		}
		
		if (map[x][y] == 'B') {
			if (blue_weight > weight) {
				blue_weight = weight;
			}
			return;
		}
		
		wall[x][y] = true;
		for (int i=0; i<4; i++) {
			int new_x = x + EWSN_X[i];
			int new_y = y + EWSN_Y[i];
			
			findBlue(new_x, new_y, weight+1);
		}
		wall[x][y] = false;
	}
}

 

 

모르겠어서  AI한테 부탁 중,.

아무래도 짤리지 않으려면 공부 열심히 해야겠구나

 

두번째 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class AD230120 {
	public static final int X = 0;
	public static final int Y = 1;
	public static final int[] EWSN_X = { 1, -1, 0, 0 };
	public static final int[] EWSN_Y = { 0, 0, 1, -1 };
	
	public static int N;
	public static int M;
	public static char[][] map;
	public static boolean[][] visitedForRed;
	public static boolean[][] visitedForEnd;
	public static boolean[][] visitedForBlue;
	public static boolean[][] visitedForDest;
	
	public static int[] red_position;
	public static int[] blue_position;
	
	public static int red_weight;
	public static int blue_weight;
	public static int dest_weight;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		for (int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			map = new char[N+1][M+1];
			visitedForRed = new boolean[N+1][M+1];
			visitedForEnd = new boolean[N+1][M+1];
			visitedForBlue = new boolean[N+1][M+1];
			visitedForDest = new boolean[N+1][M+1];
			
			red_position = new int[2];
			blue_position = new int[2];
			
			red_weight = Integer.MAX_VALUE;
			blue_weight = Integer.MAX_VALUE;
			dest_weight = Integer.MAX_VALUE;
			
			int answer = 0;
			
			for (int n=0; n<N; n++) {
				String line = br.readLine();
				for (int m=0; m<M; m++) {
					char elem = line.charAt(m);
					map[n+1][m+1] = elem;

					if (elem == 'X') {
						visitedForRed[n+1][m+1] = true;
						visitedForEnd[n+1][m+1] = true;
						visitedForBlue[n+1][m+1] = true;
						visitedForDest[n+1][m+1] = true;
					} else if (elem == 'R') {
						red_position[X] = n+1;
						red_position[Y] = m+1;
					} else if (elem == 'B') {
						blue_position[X] = n+1;
						blue_position[Y] = m+1;
					}
				}
			}
			
			// 빨간 풍선을 찾아라
			findRed(1, 1, 0);
			if (red_weight == Integer.MAX_VALUE) {
				System.out.printf("#%d -1\n", tc);
				continue;
			}
			answer += red_weight;
			
			// 빨간 풍선 버리고 파란 풍선을 찾아라
			wasteRedFindBlue(red_position[X], red_position[Y], 0);
			if (blue_weight == Integer.MAX_VALUE) {
				System.out.printf("#%d -1\n", tc);
				continue;
			}
			answer += blue_weight;
			
			// 종점 가기
			goDestination(blue_position[X], blue_position[Y], 0);
			if (dest_weight == Integer.MAX_VALUE) {
				System.out.printf("#%d -1\n", tc);
				continue;
			}
			answer += dest_weight;
			System.out.printf("#%d %d\n", tc, answer);
		}
	}
	
	public static void goDestination(int x, int y, int weight) {
		if (x < 1 || x > N || 
				y < 1 || y > M || 
				visitedForDest[x][y] || 
				dest_weight <= weight) {
			return;
		}
		
		if (x == N && y == M) {
			if (dest_weight > weight) {
				dest_weight = weight;
			}
			return;
		}
		
		visitedForDest[x][y] = true;
		for (int i=0; i<4; i++) {
			int new_x = x + EWSN_X[i];
			int new_y = y + EWSN_Y[i];
			
			goDestination(new_x, new_y, weight+1);
		}
		visitedForDest[x][y] = false;
	}
	
	public static void findRed(int x, int y, int weight) {
		if (x < 1 || x > N || 
				y < 1 || y > M || 
				visitedForRed[x][y] || 
				red_weight <= weight) {
			return;
		}
		
		if (map[x][y] == 'R') {
			if (red_weight > weight) {
				red_weight = weight;
			}
			return;
		}
		
		visitedForRed[x][y] = true;
		for (int i=0; i<4; i++) {
			int new_x = x + EWSN_X[i];
			int new_y = y + EWSN_Y[i];
			
			findRed(new_x, new_y, weight+1);
		}
		visitedForRed[x][y] = false;
	}
	
	public static void wasteRedFindBlue(int x, int y, int weight) {
		if (x < 1 || x > N || 
				y < 1 || y > M) {
			int cur_x = x;
			int cur_y = y;
			
			if (x < 1) {
				cur_x = 1;
			} else if (x > N) {
				cur_x = N;
			}
			
			if (y < 1) {
				cur_y = 1;
			} else if(y > M) {
				cur_y = M;
			}
			
			findBlue(cur_x, cur_y, weight-1);
			return;
		}
		
		if (visitedForEnd[x][y]) {
			return;
		}
		
		visitedForEnd[x][y] = true;
		for (int i=0; i<4; i++) {
			int new_x = x + EWSN_X[i];
			int new_y = y + EWSN_Y[i];
			
			wasteRedFindBlue(new_x, new_y, weight+1);
		}
		visitedForEnd[x][y] = false;
	}
	
	public static void findBlue(int x, int y, int weight) {
		if (x < 1 || x > N || 
				y < 1 || y > M || 
				visitedForBlue[x][y] || 
				blue_weight <= weight) {
			return;
		}
		
		if (map[x][y] == 'B') {
			if (blue_weight > weight) {
				blue_weight = weight;
			}
			return;
		}
		
		visitedForBlue[x][y] = true;
		for (int i=0; i<4; i++) {
			int new_x = x + EWSN_X[i];
			int new_y = y + EWSN_Y[i];
			
			findBlue(new_x, new_y, weight+1);
		}
		visitedForBlue[x][y] = false;
	}
}

 

728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > SWEA' 카테고리의 다른 글

15941. 평행사변형 JAVA  (0) 2023.03.27
15231. 바이너리 트리 JAVA  (0) 2023.01.10
15758. 무한 문자열 JAVA  (1) 2023.01.06
15230. 알파벳 공부 JAVA  (0) 2023.01.05
15612. 체스판 위의 룩 배치 JAVA  (0) 2023.01.05

'Algorithm/SWEA'의 다른글

  • 현재글AD 230120 오답노트 중,.

관련글

티스토리툴바