선장 일지

• 풀이

문제 설명대로 구현하면되는 문제이다.

키는 s를 s %= ((가로 or 세로) x 2 -2)로 시간을 줄이는 것이다.

• 코드

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.InputMismatchException;

public class Main {
	static int R, C, M, answer;
	static ArrayList<Shark> sharks;
	static int[] dx = { 0, -1, 1, 0, 0 };
	static int[] dy = { 0, 0, 0, 1, -1 };

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	// 데이터
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		R = in.nextInt();
		C = in.nextInt();
		M = in.nextInt();
		answer = 0;
		sharks = new ArrayList<>();

		int r,c,s,d,z;
		for(int i = 0 ; i < M; i++) {
			r = in.nextInt();
			c = in.nextInt();
			s = in.nextInt();
			d = in.nextInt();
			z = in.nextInt();
			
			if(d == 1 || d == 2) s = s % (R*2-2);
			if(d == 3 || d == 4) s = s % (C*2-2);
			sharks.add(new Shark(r,c,s,d,z));
		}

		solve();
	}
	
	private static void solve() {
		for(int person = 1; person <= C; person++) {
			Collections.sort(sharks);
			
			// 잡아먹음
			int r = -1, c = -1;
			for(int i = 0; i < sharks.size(); i++) {
				int tempR = sharks.get(i).r;
				int tempC = sharks.get(i).c;
				
				if(r == tempR && c == tempC) {
					sharks.remove(i--);
				} else {
					r = tempR;
					c = tempC;
				}
			}
			
			for(int i = 0; i < sharks.size(); i++) {
				if(sharks.get(i).c > person)
					break;
				// 낚시
				if(sharks.get(i).c == person) {
					answer += sharks.get(i).z;
					sharks.remove(i);
					break;
				}
			}
			
			for(int i = 0; i < sharks.size(); i++) {
				r = sharks.get(i).r;
				c = sharks.get(i).c;
				int s = sharks.get(i).s;
				int d = sharks.get(i).d;
				
				// 물고기 이동
				for(int j = 0; j < s; j++) {					
					if(r + dx[d] <= 0 || c + dy[d] <= 0 || r + dx[d] >= R + 1 || c + dy[d] >= C+1) {
						if(d % 2 == 0)
							d--;
						else
							d++;
					}
					
					r += dx[d];
					c += dy[d];
				}

				sharks.get(i).SetR(r);
				sharks.get(i).SetC(c);
				sharks.get(i).SetD(d);					
			}
		}
	}
	
}

class Shark implements Comparable<Shark> {
	int r, c, s, d, z;

	public Shark(int r, int c, int s, int d, int z) {
		this.r = r;
		this.c = c;
		this.s = s;
		this.d = d;
		this.z = z;
	}
	
	public void SetR(int r) {
		this.r = r;
	}
	
	public void SetC(int c) {
		this.c = c;
	}
	
	public void SetD(int d) {
		this.d = d;
	}

	@Override
	public int compareTo(Shark o) {
		if(this.c == o.c) {
			if(this.r == o.r)			
				return -Integer.compare(this.z, o.z);
			else
				return Integer.compare(this.r, o.r);
		} else
			return Integer.compare(this.c, o.c);
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

• 풀이

우선순위큐 + bfs로 풀었다.

해당 문제는 상어가 왼쪽, 위쪽에 있으면 먼저 탐색해야 되기때문에 그냥 bfs로는 탐색이 불가하지만 우선순위큐로 거리, x, y를 고려해서 큐정렬을 해준다면 bfs로 풀 수 있다.

정렬 기준은 거리가 다르다면 거리 순으로 오름차순, y축 좌표가 다르다면 y축 좌표로 오름차순 모두 같다면 x축 좌표로 오름차순 정렬했다.

• 코드

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.InputMismatchException;
import java.util.PriorityQueue;

public class Main {
	static int N, x, y, answer;
	static int[][] array;
	static Shark shark;
	static int[] dx = { 0, -1, 1, 0 };
	static int[] dy = { 1, 0, 0, -1 };

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	// 데이터
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		N = in.nextInt();
		array = new int[N][N];
		answer = 0;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				array[i][j] = in.nextInt();
				if (array[i][j] == 9) {
					shark = new Shark(i,j,0);
					array[i][j] = 0;
				}
			}
		}

		bfs();
	}

	private static void bfs() {
		int size = 2;
		int eat = 0; // 먹은 물고기 수

		while (true) {
			PriorityQueue<Shark> queue = new PriorityQueue<>();
			boolean[][] check = new boolean[N][N];

			queue.add(new Shark(shark.x, shark.y, 0)); // x좌표, y좌표, 이동한 거리
			check[shark.x][shark.y] = true;

			boolean sharkEat = false;

			while (!queue.isEmpty()) {
				shark = queue.poll();

				if (array[shark.x][shark.y] != 0 && array[shark.x][shark.y] < size) { // 먹이가 있으면서 상어의
					array[shark.x][shark.y] = 0; // 물고기 제거
					eat++;
					answer += shark.distance; // 움직인 거리를 총 움직인 거리에 추가
					sharkEat = true;
					break;
				}

				for (int direction = 0; direction < 4; direction++) {
					int r = shark.x + dx[direction];
					int c = shark.y + dy[direction];

					if (r < 0 || c < 0 || c >= N || r >= N || check[r][c] || array[r][c] > size)
						continue;

					queue.add(new Shark(r, c, shark.distance + 1));
					check[r][c] = true;
				}
			}

			if (!sharkEat) // 큐가 비워질 때까지 먹이를 먹은적이 없다면, 더 이상 먹은 물고기가 없으므로 탈출
				break;

			if (size == eat) { // 사이즈와 먹이를 먹은 수가 동일하다면 상어의 크기를 증가
				size++;
				eat = 0;
			}
		}

	}
}

class Shark implements Comparable<Shark> {
	int x;
	int y;
	int distance;

	public Shark(int x, int y, int distance) {
		this.x = x;
		this.y = y;
		this.distance = distance;
	}

	@Override
	public int compareTo(Shark o) {
		if(this.distance != o.distance)
			return Integer.compare(this.distance, o.distance);
		else {
			if(this.x != o.x)
				return Integer.compare(this.x, o.x);
			else
				return Integer.compare(this.y, o.y);
		}
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

• 풀이

문제 설명대로 봄, 여름, 가을, 겨울에 해야될 일들을 메소드로 나누어서 풀었다.

• 코드

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.InputMismatchException;

public class Main {
	static int N, M, K;
	static int[][] array, foodForTree;
	static ArrayList<Tree> tree;
	static ArrayList<Tree> livedTree;
	static ArrayList<Tree> deadTree;
	static int[] dx = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static int[] dy = { -1, 0, 1, -1, 1, -1, 0, 1 };

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(tree.size());
	}

	// 데이터
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		N = in.nextInt();
		M = in.nextInt();
		K = in.nextInt();
		array = new int[N + 1][N + 1];
		tree = new ArrayList<>();
		foodForTree = new int[N + 1][N + 1];

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				foodForTree[i][j] = in.nextInt();
				array[i][j] = 5;
			}
		}

		for(int i = 0; i < M; i++)
			tree.add(new Tree(in.nextInt(), in.nextInt(), in.nextInt()));

		Solve();
	}

	private static void Solve() {
		while (K-- > 0) {
			livedTree = new ArrayList<>();
			deadTree = new ArrayList<>();
			Collections.sort(tree);	// 정렬
			ComeSpring();
			ComeSummer();
			ComeFall();
			ComeWinter();
		}
	}

	private static void ComeSpring() {
		for (int i = 0; i < tree.size(); i++) {			
			Tree t = tree.get(i);
			
			// 양분이 충분한 경우 양분을 먹는다.
			if(array[t.x][t.y] >= t.age) {
				array[t.x][t.y] -= t.age;
				t.age++;				
				livedTree.add(t);
			} else {
				// 그렇지 못한 경우 죽음
				deadTree.add(t);
			}
		}
		tree.clear();
		tree.addAll(livedTree);
	}

	private static void ComeSummer() {
		// 죽은 나무 양분
		for (int i = 0; i < deadTree.size(); i++) {
			Tree t = deadTree.get(i);
			array[t.x][t.y] += t.age / 2;
		}
	}

	private static void ComeFall() {
		for (int i = 0; i < tree.size(); i++) {
			if(tree.get(i).age % 5 != 0) continue;
			
			int x = tree.get(i).x;
			int y = tree.get(i).y;
			
			for(int direction = 0; direction < 8; direction++) {
				int r = x + dx[direction];
				int c = y + dy[direction];
				if(r <= 0 || c <= 0 || r > N || c > N) continue;
				
				tree.add(new Tree(r, c, 1));
			}
		}
	}

	private static void ComeWinter() {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				array[i][j] += foodForTree[i][j];
			}
		}
	}
}

class Tree implements Comparable<Tree>{
	int x;
	int y;
	int age;

	public Tree(int x, int y, int age) {
		this.x = x;
		this.y = y;
		this.age = age;
	}
	
	@Override
	public int compareTo(Tree t) {
		return this.age - t.age;
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

• 시간초과 났던 코드

달라진점 : queue 부분을 arraylist로 고쳐줌

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int N, M, K;
	static int[][] array, foodForTree;
	static ArrayList<Tree> tree;
	static Queue<Tree> diedTree;
	static int[] dx = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static int[] dy = { -1, 0, 1, -1, 1, -1, 0, 1 };

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(tree.size());
	}

	// 데이터
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		N = in.nextInt();
		M = in.nextInt();
		K = in.nextInt();
		array = new int[N + 1][N + 1];
		tree = new ArrayList<>();
		diedTree = new LinkedList<>();
		foodForTree = new int[N + 1][N + 1];

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				foodForTree[i][j] = in.nextInt();
				array[i][j] = 5;
			}
		}

		for(int i = 0; i < M; i++)
			tree.add(new Tree(in.nextInt(), in.nextInt(), in.nextInt()));

		Solve();
	}

	private static void Solve() {
		while (K-- > 0) {
			Collections.sort(tree);	// 정렬
			ComeSpring();
			ComeSummer();
			ComeFall();
			ComeWinter();
		}
	}

	private static void ComeSpring() {
		for (int i = 0; i < tree.size(); i++) {			
			int x = tree.get(i).x;
			int y = tree.get(i).y;
			int age = tree.get(i).age;
			// 양분이 충분한 경우 양분을 먹는다.
			if(array[x][y] >= age) {
				array[x][y] -= age;
				tree.get(i).age++;
			} else {
				// 그렇지 못한 경우 죽음
				diedTree.add(new Tree(x,y,age));
				tree.remove(i);
				i--;
			}
		}
	}

	private static void ComeSummer() {
		// 죽은 나무가 양분으로 변함
		while(!diedTree.isEmpty()) {
			Tree temp = diedTree.poll();
			array[temp.x][temp.y] += temp.age /2;
		}
	}

	private static void ComeFall() {
		for (int i = 0; i < tree.size(); i++) {
			if(tree.get(i).age % 5 != 0) continue;
			
			int x = tree.get(i).x;
			int y = tree.get(i).y;
			
			for(int direction = 0; direction < 8; direction++) {
				int r = x + dx[direction];
				int c = y + dy[direction];
				if(r <= 0 || c <= 0 || r > N || c > N) continue;
				
				tree.add(new Tree(r, c, 1));
			}
		}
	}

	private static void ComeWinter() {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				array[i][j] += foodForTree[i][j];
			}
		}
	}
}

class Tree implements Comparable<Tree>{
	int x;
	int y;
	int age;

	public Tree(int x, int y, int age) {
		this.x = x;
		this.y = y;
		this.age = age;
	}
	
	@Override
	public int compareTo(Tree t) {
		return this.age - t.age;
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

• 런타임 에러떳던 코드 (IllegalArgument)

return 0부분이 잘못되었다고하는데 잘 모르겠다..

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
	static int N, M, K;
	static int[][] array, foodForTree;
	static ArrayList<Tree> tree;
	static Queue<int []> diedTree;
	static int[] dx = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static int[] dy = { -1, 0, 1, -1, 1, -1, 0, 1 };

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(tree.size());
	}

	// 데이터
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		N = in.nextInt();
		M = in.nextInt();
		K = in.nextInt();
		array = new int[N + 1][N + 1];
		tree = new ArrayList<>();
		diedTree = new LinkedList<>();
		foodForTree = new int[N + 1][N + 1];

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				foodForTree[i][j] = in.nextInt();
				array[i][j] = 5;
			}
		}

		for(int i = 0; i < M; i++)
			tree.add(new Tree(in.nextInt(), in.nextInt(), in.nextInt()));

		Solve();
	}

	private static void Solve() {
		while (K-- > 0) {
			Collections.sort(tree, new TreeCompare());	// 정렬
			ComeSpring();
			ComeSummer();
			ComeFall();
			ComeWinter();
		}
	}

	private static void ComeSpring() {
		for (int i = 0; i < tree.size(); i++) {
			int x = tree.get(i).x;
			int y = tree.get(i).y;
			int age = tree.get(i).age;
			// 양분이 충분한 경우 양분을 먹는다.
			if(array[x][y] >= age) {
				array[x][y] -= age;
				tree.get(i).age++;
			} else {
				// 그렇지 못한 경우 죽음
				diedTree.add(new int[] {x,y,age});
				tree.remove(i);
				i--;
			}
		}
	}

	private static void ComeSummer() {
		// 죽은 나무가 양분으로 변함
		while(!diedTree.isEmpty()) {
			int[] temp = diedTree.poll();
			array[temp[0]][temp[1]] += temp[2] /2;
		}
	}

	private static void ComeFall() {
		for (int i = 0; i < tree.size(); i++) {
			if(tree.get(i).age % 5 != 0) continue;
			
			int x = tree.get(i).x;
			int y = tree.get(i).y;
			int age = tree.get(i).age;
			for(int direction = 0; direction < 8; direction++) {
				int r = x + dx[direction];
				int c = y + dy[direction];
				if(r <= 0 || c <= 0 || r > N || c > N) continue;
				
				tree.add(new Tree(r, c, 1));
			}
		}
	}

	private static void ComeWinter() {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				array[i][j] += foodForTree[i][j];
			}
		}
	}
}

class Tree{
	int x;
	int y;
	int age;

	public Tree(int x, int y, int age) {
		this.x = x;
		this.y = y;
		this.age = age;
	}
}

class TreeCompare implements Comparator<Tree> {
	int ret = 0;

	@Override
	public int compare(Tree t1, Tree t2) {
		if (t1.x == t2.x && t1.y == t2.y) {
			if (t1.age < t2.age) {
				ret = -1;
			} else
				ret = 1;
		}
		return ret;
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

• 풀이

1. 연합을 할 수 있는 나라가 있는지 찾는다.

2. 찾으면 인구를 (연합 나라 인구수 합) / (연합 나라 수) 나누어 준다.

3. 없으면 종료하고 있으면 1, 2번의 작업을 다시 한다.

• 코드

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {
	static int N, L, R, answer;
	static int[][] array;
	static boolean[][] check;
	static Queue<int []> queue;
	static ArrayList<int []> union;
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1}; 
	
	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	// 데이터
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		N = in.nextInt();
		L = in.nextInt();
		R = in.nextInt();
		array = new int[N][N];
		queue = new LinkedList<>();
		union = new ArrayList<int []>();
		answer = 0;
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				array[i][j] = in.nextInt();
			}
		}
		
		MovePopulation();
	}
	
	private static void MovePopulation() {
		while(PossibleMovePopulition()) {
			answer++;
		}
	}
	
	private static boolean PossibleMovePopulition() {
		boolean possible = false;
		check = new boolean[N][N];
		
		for(int i = 0 ; i < N; i++) {
			for(int j = 0 ; j < N; j++) {
				if(!check[i][j] && FindUnion(i,j)) {
					possible = true;
				}
			}
		}		
		return possible;
	}
	
	private static boolean FindUnion(int i, int j) {
		boolean possible = false;
		queue.add(new int[] {i,j});
		check[i][j] = true;
		int sum = array[i][j];
		union.add(new int[] {i,j});
		
		while(!queue.isEmpty()) {
			int[] location = queue.poll();
			
			for(int direction = 0; direction < 4; direction++) {
				int r = location[0] + dx[direction];
				int c = location[1] + dy[direction];
				
				if(r < 0 || c < 0 || r >= N || c >= N || check[r][c]) continue;
				int gap = Math.abs(array[location[0]][location[1]] - array[r][c]);
				
				if(L <= gap && gap <= R) {
					union.add(new int[] {r,c});
					check[r][c] = true;
					queue.add(new int[] {r,c});
					sum += array[r][c];
				}
			}
		}
		
		if(sum > array[i][j]) {
			SharePopulation(sum);
			possible = true;
		}
		
		return possible;
	}
	
	private static void SharePopulation(int sum) {
		for(int index = 0; index < union.size(); index++) {
			array[union.get(index)[0]][union.get(index)[1]] = sum / union.size();
		}
		union.clear();
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

• 풀이

주사위 위쪽면을 1 아래쪽면을6 오른쪽 3 왼쪽 2  앞면 5 뒷면 4로 두고 조건대로 풀었다.

• 코드

import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int N, M, x, y, K;
	static int[][] array;
	static int[] dice;
	static int dx[] = { 0, 0, -1, 1 };
	static int dy[] = { 1, -1, 0, 0 };
	static StringBuilder sb;
	static Queue<Integer> queue;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(sb);
	}

	// 데이터
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		N = in.nextInt();
		M = in.nextInt();
		x = in.nextInt();
		y = in.nextInt();
		K = in.nextInt();
		array = new int[N][M];
		sb = new StringBuilder();
		queue = new LinkedList<>();
		dice = new int[7];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				array[i][j] = in.nextInt();
			}
		}

		for (int i = 0; i < K; i++) {
			queue.add(in.nextInt());
		}

		direction();
	}

	private static void direction() {
		while (!queue.isEmpty()) {
			int d = queue.poll();
			int r = x + dx[d - 1];
			int c = y + dy[d - 1];

			if (r < 0 || c < 0 || r >= N || c >= M)
				continue;

			RollDice(d);
			
			if (array[r][c] == 0) {
				array[r][c] = dice[6];
			} else {
				dice[6] = array[r][c];
				array[r][c] = 0;
			}
			x = r;
			y = c;

			sb.append(dice[1]).append("\n");
		}
	}

	private static void RollDice(int direction) {
		int[] temp = new int[7];
		for (int i = 1; i <= 6; i++) {
			temp[i] = dice[i];
		}

		switch (direction) {
		case 1: // 동
			dice[1] = temp[2];
			dice[3] = temp[1];
			dice[6] = temp[3];
			dice[2] = temp[6];
			break;
		case 2: // 서
			dice[1] = temp[3];
			dice[2] = temp[1];
			dice[6] = temp[2];
			dice[3] = temp[6];
			break;
		case 3: // 북
			dice[4] = temp[1];
			dice[6] = temp[4];
			dice[5] = temp[6];
			dice[1] = temp[5];
			break;
		case 4: // 남
			dice[5] = temp[1];
			dice[6] = temp[5];
			dice[4] = temp[6];
			dice[1] = temp[4];
			break;
		}

	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

• 풀이

움직일 톱니 바퀴 기준 왼쪽, 오른쪽으로 돌려준다.

톱니바퀴가 서로 맞닿는 index는 왼쪽은  6, 오른쪽은 2로 다른 경우에만 돌려준다.

방향이 1이면 시계, -1이면 반시계 방향으로 돌려준다.

• 코드

import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;

public class Main {
	static int answer;
	static int[][] array;
	
	public static void main(String[] args) throws Exception {
		SetData();
        System.out.println(answer);
	}

	// 데이터
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		array = new int[4][8];
		for(int i = 0; i < 4; i++) {
			String s = in.nextLine();
			for(int j = 0; j < 8; j++) {
				array[i][j] = s.charAt(j) - '0';
			}
		}
		
		int K = in.nextInt();
		for(int i = 0; i < K; i++) {
			TurnCogWheel(in.nextInt() - 1, in.nextInt());
		}
		
        answer = 0;
        int value = 1;
        for (int i = 0; i < 4; i++) {
        	answer += array[i][0] * value;
        	value *= 2;
        }
	}
	
	private static void TurnCogWheel(int wheelNumber, int direction) {
        left(wheelNumber - 1, -direction);
        right(wheelNumber + 1, -direction);
        rotate(wheelNumber, direction);
	}

    static void left(int wheelNumber, int direction) {
        if (wheelNumber < 0) return;

        if (array[wheelNumber][2] != array[wheelNumber + 1][6]) {
            left(wheelNumber - 1, -direction);
            rotate(wheelNumber, direction);
        }
    }

    static void right(int wheelNumber, int direction) {
        if (wheelNumber > 3) return;

        if (array[wheelNumber][6] != array[wheelNumber - 1][2]) {
            right(wheelNumber + 1, -direction);
            rotate(wheelNumber, direction);
        }
    }
    
    static void rotate(int wheelNumber, int direction) {
        if (direction == 1) {	// 시계
            int temp = array[wheelNumber][7];

            for (int i = 7; i > 0; i--) {
                array[wheelNumber][i] = array[wheelNumber][i - 1];
            }

            array[wheelNumber][0] = temp;

        } else {				// 반시계
            int temp = array[wheelNumber][0];

            for (int i = 0; i < 7; i++) {
                array[wheelNumber][i] = array[wheelNumber][i + 1];
            }

            array[wheelNumber][7] = temp;
        }
    }
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

• 풀이

문제 설명대로 풀었다.

(1, 1)에서 시작해서 오른쪽으로 가다가 방향을 바꿔야하면 바꾸면서 간다. (벽을 만나거나 몸을 만날 때 종료)

• 코드

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, 1, 0, -1};
	static int N, K, L, answer, r, c, direction;
	static int[][] array;
	static Queue<Direction> queue;
	static ArrayList<int []> snake;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	// 데이터
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		N = in.nextInt();
		answer = 0;
		array = new int[N + 1][N + 1];
		K = in.nextInt();
		queue = new LinkedList<>();
		snake = new ArrayList<int []>();
		snake.add(new int[] {1,1});
		direction = 1;
		
		for(int i = 0; i < K; i++)
			array[in.nextInt()][in.nextInt()] = 2;
		
		L = in.nextInt();
		for(int i = 0; i < L; i++)
			queue.add(new Direction(in.nextInt(), in.nextLine().charAt(0)));
		
		array[1][1] = 1;
		MoveSnake();
	}

	public static void MoveSnake() {
		int row = 1;
		int col = 1;
		
        while (true) {
        	// 방향 바꿔야 되는 경우 (direction 변경)
            if (!queue.isEmpty() && answer == queue.peek().count) {
            	ChangeDirection(queue.peek().direction);
                queue.poll();
            }

            r = row + dx[direction];
            c = col + dy[direction];
            snake.add(new int[] {r,c});

            answer++;
            if (r <= 0 || c <= 0 || r > N || c > N) {
                break;
            }

            if (array[r][c] == 2) { // 사과 O
                array[r][c] = 1;
            } else if (array[r][c] == 0) {    // 사과 X
                array[r][c] = 1;
                array[snake.get(0)[0]][snake.get(0)[1]] = 0;
                snake.remove(0);
            } else {
                break;
            }

            row = r;
            col = c;
        }
    }
	
	private static void ChangeDirection(char LorD) {
        if (LorD == 'D') { // 우회전
            direction = (direction + 1) % 4;
        } else if (LorD == 'L') {  // 좌회전
            direction = (direction + 3) % 4;
        }
	}
}

class Direction {
	int count;
	char direction;
	
	Direction(int count, char direction){
		this.count = count;
		this.direction = direction;
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

•  반례

#tc1

5

0

5

4 D

8 D

12 D

15 D

20 L

output:20

#################

#tc2

8
3
5 4
5 8
2 5
6
7 D
11 D
15 D
18 D
19 D
20 D

output:21

##########

#tc3

8
5
6 1
7 3
3 5
5 7
5 6
12
2 D
8 D
10 D
12 D
18 L
20 L
22 L
24 L
25 L
28 L
32 D
33 L

output:27

############

#tc4

20
13
6 15
7 18
20 14
14 13
11 9
7 10
3 18
10 10
13 13
13 5
6 9
10 4
4 3
19
17 D
36 D
41 D
54 D
56 L
57 L
63 L
68 L
72 L
73 L
76 D
79 D
82 D
85 D
87 D
93 L
105 D
110 D
114 D

output:90

############

#tc5

35
28
21 2
22 23
3 5
34 30
29 31
3 28
20 12
27 26
31 7
5 10
21 10
19 2
15 23
4 23
3 19
3 35
13 30
30 30
23 27
32 17
22 24
8 27
4 8
30 18
15 28
22 29
28 5
16 33
20
27 D
61 L
68 L
100 L
133 L
160 L
165 D
168 D
170 D
182 D
206 D
207 D
214 D
215 D
216 L
237 D
240 D
241 L
251 D
252 D

output: 237

#########

#tc6:

58
58
31 50
13 34
54 27
21 40
17 36
28 48
38 27
13 51
53 44
28 57
10 25
26 20
29 31
2 6
53 24
19 45
31 58
30 36
2 33
52 31
22 30
15 56
44 36
26 12
47 18
10 57
4 5
28 52
6 30
48 15
5 38
25 38
29 48
50 40
36 5
35 15
45 9
56 42
18 15
51 9
33 29
26 47
46 28
43 29
16 41
16 30
38 35
49 14
20 7
39 50
21 36
40 25
9 5
6 4
49 23
15 32
41 4
42 2
78
5 D
8 D
10 L
15 L
17 L
18 L
20 L
32 L
64 D
65 L
76 D
81 L
82 D
86 L
87 D
88 L
91 L
94 D
100 D
103 D
107 D
109 L
110 D
111 D
115 D
116 L
117 D
118 D
119 L
120 L
121 D
143 D
192 D
229 D
276 L
287 L
313 L
365 D
366 D
403 L
404 L
439 D
440 D
463 L
464 L
469 D
470 L
482 D
493 D
494 D
498 L
510 L
513 D
514 L
519 L
520 D
529 L
545 L
552 D
558 D
564 D
565 D
568 L
570 L
574 D
576 D
581 D
588 D
597 D
619 D
672 D
678 D
693 D
742 L
743 L
747 D
748 L
751 L

output:586

#######

#tc7

100
100
42 68
35 1
70 25
79 59
63 65
6 46
82 28
62 92
96 43
28 37
92 5
3 54
93 83
22 17
19 96
48 27
72 39
70 13
68 100
36 95
4 12
23 34
74 65
42 12
54 69
48 45
63 58
38 60
24 42
30 79
17 36
91 43
89 7
41 43
65 49
47 6
91 30
71 51
7 2
94 49
30 24
85 55
57 41
67 77
32 9
45 40
27 24
38 39
19 83
30 42
34 16
40 59
5 31
78 7
74 87
22 46
25 73
71 30
78 74
98 13
87 91
62 37
56 68
56 75
32 53
51 51
42 25
67 31
8 92
8 38
58 88
54 84
46 10
10 59
22 89
23 47
7 31
14 69
1 92
63 56
11 60
25 38
49 84
96 42
3 51
92 37
75 21
97 22
49 100
69 85
82 35
54 100
19 39
1 89
28 68
29 94
49 84
8 22
11 18
14 15
100
99 D
198 D
297 D
396 D
495 D
594 D
693 D
792 D
891 D
990 D
1089 D
1188 D
1287 D
1386 D
1485 D
1584 D
1683 D
1782 D
1881 D
1980 D
2079 D
2178 D
2277 D
2376 D
2475 D
2574 D
2673 D
2772 D
2871 D
2970 D
3069 D
3168 D
3267 D
3366 D
3465 D
3564 D
3663 D
3762 D
3861 D
3960 D
4059 D
4158 D
4257 D
4356 D
4455 D
4554 D
4653 D
4752 D
4851 D
4950 D
5049 D
5148 D
5247 D
5346 D
5445 D
5544 D
5545 D
5644 L
5645 L
5744 D
5745 D
5844 L
5845 L
5944 D
5945 D
6044 L
6045 L
6144 D
6145 D
6244 L
6245 L
6344 D
6345 D
6444 L
6445 L
6544 D
6545 D
6644 L
6645 L
6744 D
6745 D
6844 L
6845 L
6944 D
6945 D
7044 L
7045 L
7094 D
7095 L
7099 L
7101 D
7106 L
7114 D
7115 D
7117 D
7124 L
7130 L
7138 L
7142 L
7150 D

output:7118

• 풀이

dfs 방식을 사용했다.

dfs 방식

1. basecase는 상, 하, 좌, 우 5번 모두 움직였을 때

2. basecase에 걸리지않으면 상, 하, 좌, 우 1번씩 움직이며 계속 돌아간다.

• 코드

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;

public class Main {
	static int N, answer;
	static int[][] array;
	static Queue<Integer> queue;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	// 데이터
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		N = in.nextInt();
		answer = 0;
		array = new int[N][N];
		queue = new LinkedList<>();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				array[i][j] = in.nextInt();
				if (answer < array[i][j])
					answer = array[i][j];
			}
		}

		DFS(0);
	}

	private static void DFS(int count) {
		// basecase
		if (count == 5) {
			GetMaxValue();
			return;
		}

		int[][] temp = new int[N][N];
		CopyArray(temp, array);
		for(int i=1; i<=4; i++) {
			Move(i);
			DFS(count+1);
			CopyArray(array, temp);
			
		}
	}
	
	private static void GetMaxValue() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (array[i][j] > answer) {
					answer = array[i][j];
				}
			}
		}
	}

	private static void CopyArray(int[][] a, int[][] b) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				a[i][j] = b[i][j];
			}
		}
	}

	private static void Move(int direction) {

		int index, popData;
		
		switch (direction) {
		// 위
		case 1:
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (array[j][i] != 0)
						queue.offer(array[j][i]);
					array[j][i] = 0;
				}
				
				index = 0;
				while (!queue.isEmpty()) {
					popData = queue.poll();

					if (array[index][i] == 0) {
						array[index][i] = popData;
					}
					else if (array[index][i] == popData) {
						array[index][i] = popData * 2;
						index++;
					}
					else {
						index++;
						array[index][i] = popData;
					}
				}
			}
			break;

		// 아래
		case 2:
			for (int i = 0; i < N; i++) {
				for (int j = N - 1; j >= 0; j--) {
					if (array[j][i] != 0)
						queue.offer(array[j][i]);
					array[j][i] = 0;
				}

				index = N - 1;
				while (!queue.isEmpty()) {
					popData = queue.poll();

					if (array[index][i] == 0) {
						array[index][i] = popData;
					}
					else if (array[index][i] == popData) {
						array[index][i] = popData * 2;
						index--;
					}
					else {
						index--;
						array[index][i] = popData;
					}
				}
			}
			break;

		// 왼쪽
		case 3:
			for (int i = 0; i < N; i++) {
				for (int j = N - 1; j >= 0; j--) {
					if (array[i][j] != 0)
						queue.offer(array[i][j]);
					array[i][j] = 0;
				}

				index = N - 1;
				while (!queue.isEmpty()) {
					popData = queue.poll();

					if (array[i][index] == 0) {
						array[i][index] = popData;
					}
					else if (array[i][index] == popData) {
						array[i][index] = popData * 2;
						index--;
					}
					else {
						index--;
						array[i][index] = popData;
					}
				}
			}
			break;

		// 오른쪽
		case 4:
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (array[i][j] != 0)
						queue.offer(array[i][j]);
					array[i][j] = 0;
				}

				index = 0;
				while (!queue.isEmpty()) {
					popData = queue.poll();

					if (array[i][index] == 0) {
						array[i][index] = popData;
					}
					else if (array[i][index] == popData) {
						array[i][index] = popData * 2;
						index++;
					}
					else {
						index++;
						array[i][index] = popData;
					}
				}
			}
			break;

		}
	}
}

class Number {
	int number;
	boolean check;

	Number(int number, boolean check) {
		this.number = number;
		this.check = check;
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

• 메모리나 속도 측면에서 더 잘 짠코드

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;

public class Algorithm {
	static int N, answer;
	static int[][] array;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	// 데이터
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		N = in.nextInt();
		answer = 0;
		array = new int[N][N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				array[i][j] = in.nextInt();
				if (answer < array[i][j])
					answer = array[i][j];
			}
		}

		DFS(0);
	}

	private static void DFS(int count) {
		// basecase
		if (count == 5) {
			return;
		}

		int[][] temp = new int[N][N];
		CopyArray(temp, array);
		for(int i=1; i<=4; i++) {
			Move(i);
			DFS(count+1);
			CopyArray(array, temp);
			
		}
	}

	private static void CopyArray(int[][] a, int[][] b) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				a[i][j] = b[i][j];
			}
		}
	}

	private static void Move(int direction) {
		switch (direction) {
			case 1:
				for (int j = 0; j < N; j++) {
					int idx = 0;
					for (int i = 1; i < N; i++) {
						if (array[i][j] == 0) continue;
						if (array[idx][j] == array[i][j]) {
							answer = Math.max(answer, array[idx++][j] <<= 1);
							array[i][j] = 0;
						} else if (array[idx][j] == 0) {
							array[idx][j] = array[i][j];
							array[i][j] = 0;
						} else {
							array[++idx][j] = array[i][j];
							if (idx != i) array[i][j] = 0;
						}
						
					}
				}
				break;
			case 2:
				for (int i = 0; i < N; i++) {
					int idx = N - 1;
					for (int j = N - 2; j >= 0; j--) {
						if (array[i][j] == 0) continue;
						if (array[i][idx] == array[i][j]) {
							answer = Math.max(answer, array[i][idx--] <<= 1);
							array[i][j] = 0;
						} else if (array[i][idx] == 0) {
							array[i][idx] = array[i][j];
							array[i][j] = 0;
						} else {
							array[i][--idx] = array[i][j];
							if (idx != j) array[i][j] = 0;
						}
					}
				}
				break;
			case 3:
				for (int j = 0; j < N; j++) {
					int idx = N - 1;
					for (int i = N - 2; i >= 0; i--) {
						if (array[i][j] == 0) continue;
						if (array[idx][j] == array[i][j]) {
							answer = Math.max(answer, array[idx--][j] <<= 1);
							array[i][j] = 0;
						} else if (array[idx][j] == 0) {
							array[idx][j] = array[i][j];
							array[i][j] = 0;
						} else {
							array[--idx][j] = array[i][j];
							if (idx != i) array[i][j] = 0;
						}
					}
				}
				break;
			case 4:
				for (int i = 0; i < N; i++) {
					int idx = 0;
					for (int j = 1; j < N; j++) {
						if (array[i][j] == 0) continue;
						if (array[i][idx] == array[i][j]) {
							answer = Math.max(answer, array[i][idx++] <<= 1);
							array[i][j] = 0;
						} else if (array[i][idx] == 0) {
							array[i][idx] = array[i][j];
							array[i][j] = 0;
						} else {
							array[i][++idx] = array[i][j];
							if (idx != j) array[i][j] = 0;
						}
					}
				}
				break;
		}
	}
}

class Number {
	int number;
	boolean check;

	Number(int number, boolean check) {
		this.number = number;
		this.check = check;
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}