[JAVA] 백준 1726 로봇

로봇 1726 문제

접근방법

1. 길찾기 유형이라고 생각이 들어서 bfs로 풀어야겠다고 생각했습니다.
2. 기존 길찾기에서 3칸까지는 비용이 같도록 처리하면 쉽게 풀수 있다고 생각했습니다.

어려웠던점

1.메모리와 시간초과 부분이 가장 어려웠다
2.방향을 동서남북 0123 으로 처리했는데
동 <-> 서
남 <-> 북
180도 이동할때는 2를 주고 90도 이동할때는 1로 했는데 이부분 처리할때 생각할게 많아서 어려웠다..
3. 처음에는 방문체크 배열을 두고 했는데 갱신이 안돼서 바꾸다보니 메모리가 늘고 시간이 늘어났다...

꽤나 치열했다
답안보고 해결해서 굉장히 뿌듯
개선할때 객체생성해서 풀려고 하니 메모리가 많이 들어서
3차원 배열로 방향과 비용으로 처리하니 쉽게 해결할 수 있었다

// 첫 코드
import java.io.*;
import java.util.*;
public class Main {
	static int row,col,map[][][],objdir;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine()," ");
		row = Integer.parseInt(stz.nextToken());
		col = Integer.parseInt(stz.nextToken());
		int dir = 0;
		map = new int[row][col][2];
		int val =0;
		for(int i=0;i<row;i++) {
			stz = new StringTokenizer(br.readLine());
			for(int j=0;j<col;j++) {
				val =Integer.parseInt(stz.nextToken());
				if(val==1) map[i][j][0] = -1;
			}
		}
		
		stz = new StringTokenizer(br.readLine());
		int startx=Integer.parseInt(stz.nextToken())-1;
		int starty=Integer.parseInt(stz.nextToken())-1;
		dir = Integer.parseInt(stz.nextToken())-1;
		
		stz = new StringTokenizer(br.readLine());
		int endx =Integer.parseInt(stz.nextToken())-1;
		int endy = Integer.parseInt(stz.nextToken())-1;
		objdir = Integer.parseInt(stz.nextToken())-1;
		if(startx != endx || endy != starty) {
			bfs(startx,starty,dir);
		}
		if(map[endx][endy][0] == objdir)	System.out.println(map[endx][endy][1]);
		else System.out.println(map[endx][endy][1]+checkdir(objdir, map[endx][endy][0])-1);
	}
	static int dxdy[][] = {{0,0,1,-1},{1,-1,0,0}};
	private static void bfs(int startx, int starty, int dir) {
		map[startx][starty][0] = dir;
		Queue<xy> q = new LinkedList<>();
		q.offer(new xy(startx,starty));
		xy comp;
		while(!q.isEmpty()) {
			comp = q.poll();
			int pointer = map[comp.x][comp.y][0];
			int nx,ny;
			int cnt =0;
			int value=0;
			while(true) {
				for(int i=1;i<=3;i++) {
					nx = comp.x + dxdy[0][pointer]*i;
					ny = comp.y + dxdy[1][pointer]*i;
					if(0<=nx && nx<row && 0<=ny && ny<col ) {
						if(map[nx][ny][0] == -1) break;
						value = map[comp.x][comp.y][1] +checkdir(map[comp.x][comp.y][0],pointer);
						
						if(map[nx][ny][1] == 0 || map[nx][ny][1] >= value) {
							map[nx][ny][0] = pointer;
							map[nx][ny][1] = value;
							q.offer(new xy(nx, ny));
						}
					}
				}
				pointer= (pointer+1)%4; 
				if(cnt == 3) break;
				cnt ++;
			}
			
		}
	}
	static class xy{
		int x;
		int y;
		public xy(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
	static int checkdir(int before, int after) {
		int result= 0;
		if(after == before)	return 1;
		
		if(before == 0) {
			if(after == 1) return 3;
			else return 2;
		}
		else if(before == 1) {
			if(after == 0) return 3;
			else return 2;
		}
		else if(before == 2) {
			if(after == 3) return 3;
			else return 2;
		}
		else if(before == 3) {
			if(after == 2) return 3;
			else return 2;
		}
		return result;
	}
}

// 최종코드
import java.io.*;
import java.util.*;
public class boj1726 {
	static int row,col,map[][][],objdir,endx,endy;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine()," ");
		row = Integer.parseInt(stz.nextToken());
		col = Integer.parseInt(stz.nextToken());
		int dir = 0;
		map = new int[row][col][2];
		int val =0;
		for(int i=0;i<row;i++) {
			stz = new StringTokenizer(br.readLine());
			for(int j=0;j<col;j++) {
				val =Integer.parseInt(stz.nextToken());
				if(val==1) map[i][j][0] = -1;
			}
		}
		stz = new StringTokenizer(br.readLine());
		int startx=Integer.parseInt(stz.nextToken())-1;
		int starty=Integer.parseInt(stz.nextToken())-1;
		dir = Integer.parseInt(stz.nextToken())-1;
		
		stz = new StringTokenizer(br.readLine());
		endx =Integer.parseInt(stz.nextToken())-1;
		endy = Integer.parseInt(stz.nextToken())-1;
		objdir = Integer.parseInt(stz.nextToken())-1;
		if(startx != endx || endy != starty) {
			bfs(startx,starty,dir);
			System.out.println(map[endx][endy][1]);
		}else {
			System.out.println(checkdir(dir, objdir)-1);
		}
	}
	static int dxdy[][] = {{0,0,1,-1},{1,-1,0,0}};
	private static void bfs(int startx, int starty, int dir) {
		map[startx][starty][0] = dir;
		Queue<xy> q = new LinkedList<>();
		q.offer(new xy(startx,starty));
		xy comp;
		while(!q.isEmpty()) {
			comp = q.poll();
			int pointer = map[comp.x][comp.y][0];
			int nx,ny;
			int cnt =0;
			int value=0;
			while(true) {
				for(int i=1;i<=3;i++) {
					nx = comp.x + dxdy[0][pointer]*i;
					ny = comp.y + dxdy[1][pointer]*i;
					if(0<=nx && nx<row && 0<=ny && ny<col ) {
						if(map[nx][ny][0] == -1) break;
						value = map[comp.x][comp.y][1] +checkdir(map[comp.x][comp.y][0],pointer);
						
						if(map[nx][ny][1] == 0 || map[nx][ny][1] > value) {
							map[nx][ny][0] = pointer;
							map[nx][ny][1] = value;
							q.offer(new xy(nx, ny));
						}
						if(nx==endx && ny==endy) {
							if(map[nx][ny][0] != objdir) {
								map[nx][ny][1] += (checkdir(objdir,map[nx][ny][0])-1);
								map[nx][ny][0] = objdir;
							}
						}
					}
				}
				pointer= (pointer+1)%4; 
				if(cnt == 3) break;
				cnt ++;
			}
			
		}
	}
	static class xy{
		int x;
		int y;
		public xy(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
	static int checkdir(int before, int after) {
		int result= 0;
		if(after == before)	return 1;
		
		if(before == 0) {
			if(after == 1) return 3;
			else return 2;
		}
		else if(before == 1) {
			if(after == 0) return 3;
			else return 2;
		}
		else if(before == 2) {
			if(after == 3) return 3;
			else return 2;
		}
		else if(before == 3) {
			if(after == 2) return 3;
			else return 2;
		}
		return result;
	}
}