글 읽기 - Java 시간 초과 질문드립니다 ㅠㅠ

mamamau 5년 전 0

코드는 아래와 같습니다.

BFS로 해결하려 했고, 통나무의 가운데를 기준으로 상하좌우와 회전을 모두 고려하면서 진행했습니다.

어느 부분을 더 최적화 해야 할까요??

* 주석 추가했습니다.

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

public class MovingLog {
	static int N;
	static Log log;
	static int[][] map;
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	static boolean[][] visit;
	static boolean[][] rotate;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine().trim());
		map = new int[N][N];
		visit = new boolean[N][N];
		rotate = new boolean[N][N];
		ArrayList<Point> l = new ArrayList<Point>();
		for(int i=0;i<N;i++) {
			String s = br.readLine().trim();
			for(int j=0;j<N;j++) {
				if(s.charAt(j)=='B') {
					map[i][j]=2;
					l.add(new Point(i,j));
				}
				else if(s.charAt(j)=='E')
					map[i][j]=3;
				else
					map[i][j]=Character.getNumericValue(s.charAt(j));
			}
		}
        // 통나무의 첫 위치입니다.
		log = new Log(l.get(0),l.get(1),l.get(2));
		System.out.println(bfs());
	}
	
	public static int bfs() {
		int cnt = 0;
		Queue<Log> q = new LinkedList<Log>();
		q.add(log);
		while(!q.isEmpty()) {
			int qs = q.size();
			while(qs--!=0) {
				Log l = q.poll();
				Point left = l.left, middle = l.middle, right = l.right;
				visit[middle.x][middle.y]=true;
				if(chkRight(left, middle, right))
					return cnt;
				//상하좌우
				for(int i=0;i<4;i++) {
					int lx = left.x + dx[i], ly = left.y + dy[i];
					int mx = middle.x + dx[i], my = middle.y + dy[i];
					int rx = right.x + dx[i], ry = right.y + dy[i];
					// 진행하고자 하는 방향으로 움직일 수 있고 가운데를 중심으로 이동이 가능하다면 진행합니다.
					if(chk(lx,ly) && chk(mx,my) && chk(rx,ry) && !visit[mx][my])
						q.add(new Log(new Point(lx,ly), new Point(mx,my), new Point(rx,ry)));
				}
				//회전이 가능하다면 시키고, 한 번 회전한 자리에선 다시 회전을 하지 못하게 했습니다.
				if(chkRotate(l) && !rotate[middle.x][middle.y]) {
					rotate[middle.x][middle.y]=true;
					if(left.x==middle.x)
						q.add(new Log(new Point(left.x-1,left.y+1),middle,new Point(right.x+1,right.y-1)));
					else
						q.add(new Log(new Point(left.x+1,left.y-1),middle,new Point(right.x-1,right.y+1)));
				}
			}
			cnt++;
		}
		return 0;
	}
	// 범위를 벗어나거나, 나무에 부딪히는 지 검사하는 과정입니다.
	public static boolean chk(int x, int y) {
		return (x>=0 && x<N && y>=0 && y<N) && (map[x][y]!=1);
	}
	// 목적지에 도달했는 지 검사하는 과정입니다.
	public static boolean chkRight(Point l, Point m, Point r) {
		if(map[l.x][l.y]==3 && map[m.x][m.y]==3 && map[r.x][r.y]==3)
			return true;
		return false;
	}
	// 회전가능 여부 검사 메소드입니다.
	public static boolean chkRotate(Log l) {
		int mx = l.middle.x, my = l.middle.y;
		if(chk(mx-1,my-1) && chk(mx+1,my+1)) {
			for(int i=mx-1;i<=mx+1;i++) {
				for(int j=my-1;j<=my+1;j++) {
					if(map[i][j]==1)
						return false;
				}
			}
		} else
			return false;
		return true;
	}
    
	public static class Log {
		public Point left;
		public Point middle;
		public Point right;
		public Log(Point left, Point middle, Point right) {
			this.left=left; this.middle=middle; this.right=right;
		}
	}
	
	public static class Point {
		public int x;
		public int y;
		public Point(int x, int y) {
			this.x=x; this.y=y;
		}
	}
}

djm03178 5년 전 0

BFS는 pop 할 때 방문 체크를 하는 것이 아니라 push할 때 방문 체크를 해야 중복 방문이 일어나지 않습니다. https://www.acmicpc.net/board/... 랑 문제는 다르지만 똑같은 상황입니다.

mamamau 5년 전 0

말씀해 주신 부분을 고쳐봤는데도 시간 초과가 뜹니다.

코드가 잘못된 건가요? 아니면 큐에 Log 클래스를 넣는 게 원인일까요?

        if(chk(lx,ly) && chk(mx,my) && chk(rx,ry) && !visit[mx][my]) {
			q.add(new Log(new Point(lx,ly), new Point(mx,my), new Point(rx,ry)));
			visit[middle.x][middle.y]=true;
		}

djm03178 5년 전 0

mx, my랑 middle.x, middle.y는 다르지 않나요? visit[mx][my]로 검사하는데 체크는 visit[middle.x][middle.y]로 하는 이유가 있나요?

mamamau 5년 전 0

아;; 멘탈이 터져서 급하게 한다고 실수를 했네요... mx my가 맞습니다.

덕분에 해결할 수 있었습니다. 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

Java 시간 초과 질문드립니다 ㅠㅠ

mamamau 5년 전 0

djm03178 5년 전 0

mamamau 5년 전 0

djm03178 5년 전 0

mamamau 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말