728x90
시뮬레이션 중에 삼성 A형에 나올만한 시뮬레이션이었다. 이문제의 중점을 어떤 것을 기준으로 어떻게 방문 처리를 하냐인 것이다.
해결 방법은 중점을 가지고 가로,세로,를 방문처리로 판단해주는 것이다.
풀이 방법
- 통나무 중앙을 기준으로 가로 세로를 판정
- 가로, 세로 각각 위,아래,좌,우 갈 수 있는지 확인 후 이동 후 큐에 넣기
- 가로, 세로 각각 중앙점을 기준으로 8방향 즉 대각선 까지 검사 후 회전 가능하면 회전 후 큐에 넣기
- 계속해서 시뮬레이션 진행~
중앙점과 이동횟수 가로, 세로인지 판단할 변수를 class에 지정
그림처럼 맨끝의 지점을 찾은 뒤 가운뎃점을 찾는 과정
BFS에서 통나무가 위치할 통나무와 일치한지 찾으면 return~
그림처럼 통나무가 세로로 되어있다면
중앙점에서 2위로 이동한 지점 검사 후 방문 안 했으면 큐에
마찬가지로 오른쪽으로 1칸 이동했을 때 모든점이 1에 없거나 범위 안일 때
중앙점에서 2 아래로 이동한 지점 검사 후 방문 안 했으면 큐에
마찬가지로 왼쪽으로 1칸 이동했을 때 모든 점이 1에 없거나 범위 안일 때
이렇게 가로일 때도 각각 처리해줘야 한다.
또한 마찬가지로
이렇게 회전이 가능한지 확인을 하고 난 뒤 방문 안 했으면 회전을 시켜준다.
생각해보면 하란대로만 할 수 있다면 풀 수 있는 문제이다. 기존에는 소스를 생각나는 대로 짜서 통과는 했지만 지저분해서 생각을 정리하고 다시 짜서 깔끔해졌다.
전체 코드
더보기
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main{
public static class mal {
Point p;
int dir;// 0는 가로 1는 세로
int count;
public mal(Point p, int dir, int count) {
this.p = p;
this.dir = dir;
this.count = count;
}
}
static String map[][];
static int resultdir,startdir,dir[][] = { { -1, 0 },{ 0, -1 }, { 0, 1 }, { 1, 0 } }, n,con,dirw[][]= {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
static boolean visit[][][];
static Point resultp, startp;
static Queue<mal> q;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
q=new LinkedList<mal>();
n = Integer.parseInt(br.readLine());
map = new String[n][n];
visit = new boolean[n][n][2];
for (int i = 0; i < n; i++) {
String s = br.readLine();
for (int j = 0; j < n; j++) {
map[i][j] = "";
map[i][j] += s.charAt(j);
if (map[i][j].equals("B")) {
startp = new Point(i, j);
} else if (map[i][j].equals("E")) {
resultp = new Point(i, j);
}//가장 끝의 위치를 찾아줌
}
}
for (int i = 0; i < 2; i++) {
if(startp.x+dir[i][0]<0||startp.y+dir[i][1]<0) {
continue;
}
else if(map[startp.x+dir[i][0]][startp.y+dir[i][1]].equals("B")){
startdir=i;
startp.x+=dir[i][0];
startp.y+=dir[i][1];
visit[startp.x][startp.y][startdir]=true;
}
}//시작점의 위치가 세로인지 가로인지
q.add(new mal(startp,startdir,0));//시작점 넣어준다
for (int i = 0; i < 2; i++) {
if(resultp.x+dir[i][0]<0||resultp.y+dir[i][1]<0) {
continue;
}
else if(map[resultp.x+dir[i][0]][resultp.y+dir[i][1]].equals("E")){
resultdir=i;
resultp.x+=dir[i][0];
resultp.y+=dir[i][1];
}
}//도착점
bfs();
System.out.println(con);
}
private static void bfs() {
// TODO Auto-generated method stub
while(!q.isEmpty()) {
mal next=q.remove();
if(next.p.x==resultp.x&&next.p.y==resultp.y&&resultdir==next.dir) {
con=next.count;
return;
}
boolean flag=true;
if(next.dir==0) {//세로
if(next.p.x-2>=0){//위
if(map[next.p.x-2][next.p.y].equals("1"))
flag=false;
else if(visit[next.p.x-1][next.p.y][next.dir]) {
flag=false;
}
if(flag) {
visit[next.p.x-1][next.p.y][next.dir]=true;
q.add(new mal(new Point(next.p.x-1,next.p.y),next.dir,next.count+1));
}
}
flag=true;
if(next.p.y+1<n) {//오른쪽
if(map[next.p.x-1][next.p.y+1].equals("1")||map[next.p.x][next.p.y+1].equals("1")||map[next.p.x+1][next.p.y+1].equals("1"))
flag=false;
else if(visit[next.p.x][next.p.y+1][next.dir]) {
flag=false;
}
if(flag) {
visit[next.p.x][next.p.y+1][next.dir]=true;
q.add(new mal(new Point(next.p.x,next.p.y+1),next.dir,next.count+1));
}
}
flag=true;
if(next.p.x+2<n) {//아래
if(map[next.p.x+2][next.p.y].equals("1"))
flag=false;
else if(visit[next.p.x+1][next.p.y][next.dir]) {
flag=false;
}
if(flag) {
visit[next.p.x+1][next.p.y][next.dir]=true;
q.add(new mal(new Point(next.p.x+1,next.p.y),next.dir,next.count+1));
}
}
flag=true;
if(next.p.y-1>=0) {//왼쪽
if(map[next.p.x-1][next.p.y-1].equals("1")||map[next.p.x][next.p.y-1].equals("1")||map[next.p.x+1][next.p.y-1].equals("1"))
flag=false;
else if(visit[next.p.x][next.p.y-1][next.dir]) {
flag=false;
}
if(flag) {
visit[next.p.x][next.p.y-1][next.dir]=true;
q.add(new mal(new Point(next.p.x,next.p.y-1),next.dir,next.count+1));
}
}
}
else {//가로
if(next.p.x-1>=0){//위
if(map[next.p.x-1][next.p.y-1].equals("1")||map[next.p.x-1][next.p.y].equals("1")||map[next.p.x-1][next.p.y+1].equals("1"))
flag=false;
else if(visit[next.p.x-1][next.p.y][next.dir]) {
flag=false;
}
if(flag) {
visit[next.p.x-1][next.p.y][next.dir]=true;
q.add(new mal(new Point(next.p.x-1,next.p.y),next.dir,next.count+1));
}
}
flag=true;
if(next.p.y+2<n) {//오른쪽
if(map[next.p.x][next.p.y+2].equals("1"))
flag=false;
else if(visit[next.p.x][next.p.y+1][next.dir]) {
flag=false;
}
if(flag) {
visit[next.p.x][next.p.y+1][next.dir]=true;
q.add(new mal(new Point(next.p.x,next.p.y+1),next.dir,next.count+1));
}
}
flag=true;
if(next.p.x+1<n) {//아래
if(map[next.p.x+1][next.p.y-1].equals("1")||map[next.p.x+1][next.p.y].equals("1")||map[next.p.x+1][next.p.y+1].equals("1"))
flag=false;
else if(visit[next.p.x+1][next.p.y][next.dir]) {
flag=false;
}
if(flag) {
visit[next.p.x+1][next.p.y][next.dir]=true;
q.add(new mal(new Point(next.p.x+1,next.p.y),next.dir,next.count+1));
}
}
flag=true;
if(next.p.y-2>=0) {//왼쪽
if(map[next.p.x][next.p.y-2].equals("1"))
flag=false;
else if(visit[next.p.x][next.p.y-1][next.dir]) {
flag=false;
}
if(flag) {
visit[next.p.x][next.p.y-1][next.dir]=true;
q.add(new mal(new Point(next.p.x,next.p.y-1),next.dir,next.count+1));
}
}
}
turn(next);
}
}
private static void turn(mal next) {
// TODO Auto-generated method stub
boolean flag=true;
for(int i=0;i<8;i++) {
int x=next.p.x+dirw[i][0];
int y=next.p.y+dirw[i][1];
if(x<0||x>=n||y<0||y>=n||map[x][y].equals("1")) {
flag=false;
break;
}
}
if(flag) {
if(next.dir==0&&!visit[next.p.x][next.p.y][1]) {
visit[next.p.x][next.p.y][1]=true;
q.add(new mal(next.p,1,next.count+1));
}
else if(next.dir==1&&!visit[next.p.x][next.p.y][0]) {
visit[next.p.x][next.p.y][0]=true;
q.add(new mal(next.p,0,next.count+1));
}
}
}
}
'알고리즘' 카테고리의 다른 글
| 백준 2589 <보물섬> (0) | 2020.09.29 |
|---|---|
| 백준 4811 <알약> (0) | 2020.09.26 |
| 백준 14466 <소가 길을 건너간 이유 6> (0) | 2020.09.16 |
| 백준 6087 <레이저 통신> (0) | 2020.09.13 |
| 백준 2174 <로봇 시뮬레이션> (0) | 2020.09.13 |
