• 풀이

 

일단 배열을 받으면서 ArrayList에 프로세스의 위치를 추가한다. (단, 가장자리는 전선이 필요없으니 추가 안함)

 

사용 방법은 dfs이다. 사용이유는 모든 경우의 수를 돌아야하고 해당 문제에서 확실하게 돌 수 있는 방법이라 생각했다.

 

DFS

1. basecase는 모든 프로세스를 돌았을 때이다.

2. basecase 안에서는 최대한 많이 연결된 프로세스의 경우 최대 전선 수를 가져온다.

3. basecase에 걸리지 않는 경우는 4방향으로 돌아야한다. (단, 프로세스가 선택되지 않을 경우도 있다.)

4. 4방향 연결이 돌 수 있는지 체크 후 돌린다. (여기선 백트래킹 사용)

 

 

  • 코드
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.InputMismatchException;

public class Solution {
	static int[][] array;
	static ArrayList<int[]> core;
	static int N, answer, maxOfConnectedCore;
	static int[] x = { -1, 0, 1, 0 };
	static int[] y = { 0, 1, 0, -1 };
	static StringBuilder sb;

	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);

		int testcase = in.nextInt();
		sb = new StringBuilder();

		for (int i = 1; i <= testcase; i++) {
			N = in.nextInt();
			array = new int[N][N];
			answer = Integer.MAX_VALUE;
			core = new ArrayList<>();

			InputArray(in);

			maxOfConnectedCore = 0;
			dfs(0, 0, 0);
			sb.append("#" + i + " " + answer).append("\n");
		}
	}

	private static void dfs(int depth, int countOfConnectedCore, int countOfLine) {
		// basecase
		if (depth == core.size()) {
			if (maxOfConnectedCore < countOfConnectedCore) {
				maxOfConnectedCore = countOfConnectedCore;
				answer = countOfLine;
			} else if (maxOfConnectedCore == countOfConnectedCore) {
				if (answer > countOfLine)
					answer = countOfLine;
			}

			return;
		}

		for (int i = 0; i < 4; i++) {
			if (CheckConnect(core.get(depth), i)) {
				int count = ConnectLine(core.get(depth), i, 2); // 연결
				dfs(depth + 1, countOfConnectedCore + 1,countOfLine + count);
				ConnectLine(core.get(depth), i, 0); // 연결 해제
			}
		}
		
		dfs(depth + 1, countOfConnectedCore, countOfLine);	// 연결 X
	}

	private static void InputArray(InputReader in) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				array[i][j] = in.nextInt();
				if (array[i][j] == 1 && i != 0 && i != N - 1 && j != 0 && j != N - 1)
					core.add(new int[] { i, j });
			}
		}
	}

	private static int ConnectLine(int[] coreIndex, int direction, int value) {
		int count = 0;
		int r = coreIndex[0] + x[direction];
		int c = coreIndex[1] + y[direction];
		while (r >= 0 && c >= 0 && r < N && c < N) {
			array[r][c] = value;
			count++;
			r = r + x[direction];
			c = c + y[direction];
		}
		return count;
	}

	private static boolean CheckConnect(int[] coreIndex, int direction) {
		int r = coreIndex[0] + x[direction];
		int c = coreIndex[1] + y[direction];
		while (r >= 0 && c >= 0 && r < N && c < N) {
			if (array[r][c] != 0)
				return false;
			r = r + x[direction];
			c = c + y[direction];
		}
		return true;
	}
}

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;
	}
}

 

16570번: 앞뒤가 맞는 수열

수열 (a1, a2, ⋯, aN) 이 다음의 성질을 가지면 그 수열은 k-앞뒤수열 이라고 한다. (a1, a2, ⋯, ak) = (aN-k+1, aN-k+2, ⋯ , aN), 1 ≤ k < N 어떤 수열이 k-앞뒤수열일 때, k의 최댓값 k*를 그 수열의 앞뒤계

www.acmicpc.net

 

 

 

 


 

 

 

  • 생각

 

 

KMP알고리즘으로 풀면 쉽게 풀 수 있을 것 같다.

 

 

 

 

  • 코드

 

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

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

	public static void main(String[] args) throws Exception {
		SetData();
	}

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

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

		for (int i = N - 1; i >= 0; i--) {
			array[i] = in.nextInt();
		}

		KMP();

		int length = 0, count = 0;
		for (int i = 0; i < N; i++) {
			if (pi[i] > length) {
				length = pi[i];
				count = 0;
			}
			if (pi[i] == length)
				count++;
		}
		if (length == 0)
			System.out.println("-1");
		else
			System.out.println(length + " " + count);
	}

	public static void KMP() {
		int j = 0;
		for (int i = 1; i < N; i++) {
			while (j > 0 && array[j] != array[i]) {
				j = pi[j - 1];
			}
			if (array[j] == array[i]) {
				pi[i] = ++j;
			}
		}
	}
}

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;
	}
}

 

 

 

  • KMP 알고리즘이 아니여도 풀 수 있는 문제이다.

 

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

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

	public static void main(String[] args) throws Exception {
		SetData();
	}

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

		N = in.nextInt();
		array = new int[N + 1];
		pi = new int[N + 1];

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

		KMP();

		for (int i = N; i >= 1; i--) {
			if (pi[i] != 0) {
				System.out.println(i + " " + pi[i]);
				System.exit(0);
			}
		}

		System.out.println(-1);
		
	}

	static void KMP() {
		for (int i = N - 1; i >= 1; i--) {
			int count = 0;
			int j = N;
			int index = i;
			while (array[index--] == array[j--]) {
				count++;
			}
			pi[count]++;
		}
	}
}

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;
	}
}

 

1786번: 찾기

첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i~i+m-1번 문자와 P의 1~m

www.acmicpc.net

 

 

 


 

 

 

  • 생각

 

O(nm)으로 풀면 쉽게 풀 수 있는 문제이지만, 시간제한으로 O(n) 시간복잡도로 풀어야하는 문제이다. 

이런 문자열(ctrl + f로 찾는 기능)을 푸는 문제에서 활용할 수 있는 알고리즘이 있다.

KMP 알고리즘으로 풀면 O(n + m)의 시간복잡도로 풀 수 있다.

 

 

  • 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.List;

public class Main {
	static StringBuilder sb;
	static int start, count;
	static List<Integer> list;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(list.size() + "\n" + sb);
	}

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

		String t = br.readLine();
		String p = br.readLine();
		sb = new StringBuilder();
		list = new ArrayList<Integer>();
		count = 0;

		KMP(t, p);
		for(int value : list) {
			sb.append(value).append(" ");
		}
	}
	
	// KMP 알고리즘 - pi[] 배열에서 주어진 문자열의 인덱스 0부터 i까지의 부분 문자열 중
	// 접두사 == 접미사가 되는 가장 긴 접두사의 길이를 넣는다.
	// 현재 밑 코드에서 접두사는 j(왼쪽), 접미사는 i(오른쪽)이다.
	static void KMP(String s, String pattern) {
		int[] pi = getPi(pattern);
		int j = 0;
		int strLen = s.length();
		int patternLen = pattern.length();
		
		for(int i = 0; i < strLen; i++) {
			while(j > 0 && s.charAt(i) != pattern.charAt(j)) { // 다르면 같았던 다음 접미사로 바로 건너뛰기 
				j = pi[j - 1];
			}
			
			if(s.charAt(i) == pattern.charAt(j)) {
				if(j + 1 == patternLen) { // pattern 문자열 전부가 같다면
					list.add(i - j + 1); // 전체 문자열 중 패턴 문자열과 같은 문자열의 시작 인덱스를 구해야 하므로(게다가 1부터 시작함)
					j = pi[j]; // 초기화
				}
				else { // 바로 다음번째 문자를 가지고 비교해야 하므로 
					j++;
				}
			}
		}
	}

	static int[] getPi(String p) {
		int[] pi = new int[p.length()];
		int j = 0;
		for (int i = 1; i < p.length(); i++) {
			while (j > 0 && p.charAt(i) != p.charAt(j)) { // j > 0 인 이유는 최소 두 글자부터 비교하기 위함
				j = pi[j - 1]; // 다르면 이전의 문자열에서 접두사 - 접미사 같은 최대 길로 이동시킨다.
			}
			if (p.charAt(i) == p.charAt(j))
				pi[i] = ++j;
		}

		return pi;
	}

}

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;
	}
}

 

5052번: 전화번호 목록

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가

www.acmicpc.net

 

 

 

 


 

 

 

 

  • 생각

 

입력한 모든 숫자 중 한 가지의 숫자가 다른 숫자에 시작으로 포함되어있으면 안되는 문제이다.

 

이때 정수로 오름차순 정렬하면 정말 크고작은 수대로 정렬이 되기때문에 원하는 대로 정렬이 안된다.

여기서 문자열로 받은다음 정렬하면 원하는대로 정렬 될것이다.

그래서 정렬 후 i-1인덱스의 값이 i인덱스의 값에 startsWith를 사용해서 접두어 관계를 가지는지 확인만 해주면 된다.

 

 

 

 

  • 코드

 

 

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

public class Main {
	static StringBuilder sb;
	static int N, L, answer;

	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);

		int testcase = in.nextInt();
		sb = new StringBuilder();
		int n;
		boolean check;
		
		for(int i=0;i<testcase;i++)
		{
			check = false;
			n = in.nextInt();
			String[] array = new String[n];
            for(int j=0;j<n;j++) {
                array[j]=in.nextLine();
            }
            
            //정렬과 스위치 구현
            Arrays.sort(array, new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return o1.compareTo(o2);                    
                }
            });
            
            for(int j=1;j<n;j++) {
                if(array[j].startsWith(array[j-1])) {
                    check=true;
                    break;
                }
            }
            
            if(check) sb.append("NO").append("\n");
            else sb.append("YES").append("\n");
		}		
	}
	
}

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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int TC = Integer.parseInt(br.readLine());

        root:
        for (int tc = 0; tc < TC; tc++) {
            int n = Integer.parseInt(br.readLine());
            HTrie root = new HTrie('r', true);
            boolean check = true;
            for (int i = 0; i < n; i++) {
                char[] input = br.readLine().toCharArray();
                if (check) {
                    if (!root.insert(input)) {
                        check = false;
                    }
                }
            }
            if (check) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }


    static class HTrie {
        char number;
        boolean isRoot;
        boolean isEnd;
        HTrie[] children;

        HTrie(char number, boolean isRoot) {
            this.number = number;
            this.isRoot = isRoot;
            children = new HTrie[10];
        }

        boolean insert(char[] numbers) {
            HTrie t = this;

            for (int i = 0; i < numbers.length; i++) {
                char c = numbers[i];
                int id = c - '0';

                if (t.children[id] == null) {
                    t.children[id] = new HTrie(c, false);
                } else {
                    if (t.children[id].isEnd && i != numbers.length - 1) {
                        return false;
                    }

                    if (i == numbers.length - 1) {
                        return false;
                    }
                }

                t = t.children[id];

                if (i == numbers.length - 1) {
                    t.isEnd = true;
                }
            }

            return true;
        }
    }
}

 

14890번: 경사로

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

www.acmicpc.net

 

 

 

 


 

 

 

  • 생각

 

바로 구현하면 되는 문제이다.

 

해당 기준으로 모든 행과 열을 확인했다.

1. 모든 행과 열은 왼쪽부터 오른쪽, 오른쪽부터 왼쪽 다 확인한다. (이전 블럭보다 작은 경우만 확인하기 때문)

2. 이전 블럭보다 -2가 작으면 해당 행이나 열은 되지 않는다.

3. 이전 블럭보다 -1이면 count를 세면서 되돌아올때 해당 블럭은 체크안하기 위해서 체크를 한다. (boolean배열 사용)

4. 이미 count가 1이상인데 이전 블럭보다 높거나 같은 블럭이 나오면 안된다.

5. count가 L만큼 되면 이전 블럭(현재 블럭으로)과 count를 초기화한다.

6. 이전 블럭보다 큰 블럭이 나오면 이전블럭을 현재 블럭으로 변경해준다.

 

 

 

 

  • 코드

 

 

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

public class Algorithm {
	static int[] x =  { -1, 0, 1, 0 };
    static int[] y = { 0, 1, 0, -1 };
	static int[][] array;
	static int N, L, answer;

	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();
		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();
			}
		}
		
		Calculate();
	}
	
	private static void Calculate() {
		// 가로
		for(int i = 0; i < N; i++) {
			// ->
			boolean check = false;		// 중간에 안되면 반복문을 중단시킬 수단
			boolean[] visit = new boolean[N];	// 겹치는 경우를 방지
			int pre = array[i][0];		// 이전 값
			int count = 0;
			for(int j = 1; j < N; j++) {
				// 이전 값보다 -2가 작으면 바로 종료
				if(pre - 1 > array[i][j]) 	{
					check = true;
					break;
				}
				
				// 이전 값 -1이면 count시작
				if(pre - 1 == array[i][j]) {
					visit[j] = true;		// 겹치는 경우 방지 (>> 갔다가 << 작업해주는데 이 경우 방지)
					count++;
				}
				
				// 이미 -1칸이 1개 나왔는데 pre값보다 큰값이 나오면 반복문 빠져나옴( L개수가 나오지 않았음)
				if(count >= 1 && pre <= array[i][j]) {
					check = true;
					break;
				}
				
				// L개수만큼 나오면 count와 pre값 초기화
				if(count >= L) {
					count = 0;
					pre = array[i][j];
				}
				
				// pre보다 큰값이 나오면 초기화
				if(pre < array[i][j]) pre = array[i][j];
			}
			if(check || (count != 0 && count < L))
				continue;
			
			// <-
			pre = array[i][N-1];
			count = 0;
			for(int j = N -2; j >= 0; j--) {
				if(pre - 1 > array[i][j]) 	{
					check = true;
					break;
				}
				
				if(pre - 1 == array[i][j]) {
					count++;
					if(visit[j]) {
						check = true;
						break;
					}
						
				}
				
				if(count >= 1 && pre <= array[i][j]) {
					check = true;
					break;
				}
				
				if(count >= L) {
					count = 0;
					pre = array[i][j];
				}
				if(pre < array[i][j]) pre = array[i][j];
			}
			if(check || (count != 0 && count < L))
				continue;
			
			answer++;
		}
		
		// 세로
		for(int i = 0; i < N; i++) {
			// 위
			boolean check = false;
			boolean[] visit = new boolean[N];
			int pre = array[0][i];
			int count = 0;
			for(int j = 1; j < N; j++) {
				if(pre - 1 > array[j][i]) 	{
					check = true;
					break;
				}
				
				if(pre - 1 == array[j][i]) {
					count++;
					visit[j] = true;
				}
				
				if(count >= 1 && pre <= array[j][i]) {
					check = true;
					break;
				}
				
				if(count >= L) {
					count = 0;
					pre = array[j][i];
				}
				if(pre < array[j][i]) pre = array[j][i];
			}
			if(check || (count != 0 && count < L))
				continue;
			
			// 밑
			pre = array[N-1][i];
			count = 0;
			for(int j = N -2; j >= 0; j--) {
				if(pre - 1 > array[j][i]) 	{
					check = true;
					break;
				}
				
				if(pre - 1 == array[j][i]) {
					count++;
					if(visit[j]) {
						check = true;
						break;
					}
						
				}
				
				if(count >= 1 && pre <= array[j][i]) {
					check = true;
					break;
				}
				
				if(count >= L) {
					count = 0;
					pre = array[j][i];
				}
				if(pre < array[j][i]) pre = array[j][i];
			}
			if(check || (count != 0 && count < L))
				continue;
			
			answer++;
		}
	}
}

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;
	}
}

 

 

 

14503번: 로봇 청소기

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어

www.acmicpc.net

 

 

 


 

 

 

 

  • 내용

NxM 크기의 직사각형의 공간을 로봇 청소기가 청소할 수 있다. 각각의 칸은 벽 또는 빈칸이다. 청소기는 동, 서, 남, 북으로 바라보는 방향이 있다.
지도의 각 칸은 (r,c)로 나타낼 수 이쏙, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.
로봇 청소기의 작동 방법은 다음과 같다.
1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
   a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향을 ㅗ회전하고 2번으로 돌아간다.
   c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌       아간다.
   d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.


 

 

 

  • 생각

 

queue를 이용해서 풀면 쉽게 풀 수 있을 것 같다. queue로 현재 위치와 방향을 offer해가면서 이동 가능할때만 queue에 넣고 4방향 모두 가지못할땐 뒤의 방향이 벽인지 확인해주고 벽이 아니면 queue에 offer, 벽이면 종료

 

 

 

 

  • 코드

 

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[] x =  { -1, 0, 1, 0 };
    static int[] y = { 0, 1, 0, -1 };
	static int[][] array;
	static Queue<int[]> queue;
	static int N, M, answer;

	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();
		M = in.nextInt();
		array = new int[N][M];
		queue = new LinkedList<>();
		queue.offer(new int[] {in.nextInt(), in.nextInt(), in.nextInt()});
		answer = 1;

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

		OperateRobot();
	}

	private static void OperateRobot() {
		while (!queue.isEmpty()) {
			int[] robot = queue.poll();
			int robotX = robot[0];
			int robotY = robot[1];
			int d = robot[2];
			// 청소
			array[robotX][robotY] = 2;

            boolean check = false;    // 4 방향 모두 갈 수 없을 때
            int r;
            int c;
            int nextD;
 
            for (int i = 0; i < 4; i++) {
                d = (d + 3) % 4;    
                r = robotX + x[d];    
                c = robotY + y[d];    

                if (r < 0 || c < 0 || r >= N || c >= M)   continue;
                
                //다음 이동할 위치가  청소되지 않은 곳이라면 간다.
                if (array[r][c] == 0) {
                    queue.add(new int[] {r,c, d});
        			answer++;
                    check = true;
                    break;
                }
            }
            
            // 네 방향 모두 청소됐거나 벽일 경우 후진
            if (!check) {
                nextD = (d + 2) % 4;
                r = robotX + x[nextD];
                c = robotY + y[nextD];
 
                // 후진을 못할 경우
                if (array[r][c] != 1) {
                    queue.add(new int[] {r, c, d});
                }
            }

		}
	}
}

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;
	}
}

 

13460번: 구슬 탈출 2

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'

www.acmicpc.net

 

 

 


 

 

 

  • 내용

 

스타트링크가 있다. 스타트링크의 테두리는 막혀있고, 스타트링크 안에는 빨간 구슬, 파란 구슬, 스타트링크를 빠져나갈 수 있는 구멍이 있다. 게임의 목표는 빨간 구슬을 스타트링크를 빠져나갈 수 있는 구멍이다.

 

빼내는 방법은 중력을 이용해서 빼내야한다. 상, 하, 좌, 우로 기울이면 중력에따라서 구슬이 움직이는 구조이다.

 

최소 몇번의 상, 하, 좌, 우로 기울여서 빨간 구슬을 스타트링크에서 빼낼 수 있는지 출력하면 된다. 단, 10번 이하로 움직여서 빼낼 수 없으면 -1을 출력한다.

 

 

 

  • 생각

 

재귀 형식으로 네 방향을 돌려가면서 10번 이하일때 골인할 때만 answer 변수를 초기화 시켜주었다.

 

 

 

 

  • 코드

 

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

public class Algorithm {
	static int[] x = { -1, 1, 0, 0 };
	static int[] y = { 0, 0, -1, 1 };
	static int N, M, answer;

	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();
		M = in.nextInt();
		char[][] array = new char[N][M];
		answer = Integer.MAX_VALUE;
		int bX = 0, bY = 0, rX = 0, rY = 0;
		
		String s;
		for(int i = 0; i < N; i++) {
			s = in.nextLine();
			for(int j = 0 ; j < M; j++) {
				array[i][j] = s.charAt(j);
				if(array[i][j] == 'B') {
					bX = i;
					bY = j;
				}
				if(array[i][j] == 'R') {
					rX = i;
					rY = j;
				}
			}
		}
		
		for(int i = 0; i < 4; i++) {
			bfs(array, i, 0, bX, bY, rX, rY);
		}
		
		if(answer == Integer.MAX_VALUE) answer = -1;
	}
	
	private static void bfs(char[][] array,int index, int count, int bX, int bY, int rX, int rY) {
		if(count > 9) {
			return;
		}
		int blueX = bX;
		int blueY = bY;
		int redX = rX;
		int redY = rY;
		/*
		System.out.println("\n");
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				System.out.print(array[i][j]);
			}
			System.out.println();
		}*/
			
		
		boolean check = false, check2 = false;
		while(true) {
			// move
			blueX += x[index];
			blueY += y[index];
			redX += x[index];
			redY += y[index];
			
			// 움직일 수 없는 경우
			if((array[blueX][blueY] == '#' || (blueX + x[index] == redX && blueY + y[index] == redY)) &&
					(array[redX][redY] == '#' || (redX + x[index] == blueX && redY + y[index] == blueY))) {
				blueX -= x[index];
				blueY -= y[index];
				redX -= x[index];
				redY -= y[index];
				if(array[blueX+x[index]][blueY+y[index]] == 'O')
					check = true;
				break;
			}
			
			// 앞이 막혀있는 경우
			if(array[blueX][blueY] == '#') {
				blueX -= x[index];
				blueY -= y[index];
			}
			
			if(array[redX][redY] == '#') {
				redX -= x[index];
				redY -= y[index];
			}
			
			// 골인
			if(array[redX][redY] == 'O') {
				check2 = true; 
			}
			
			// 잘못된 골인
			if(array[blueX][blueY] == 'O') {
				check = true;
				break;				
			}
			
		}
		
		if(!check && check2) {
			answer = Math.min(answer, count+1);
			return;
		}
		
		if(!check) {
			char temp = array[blueX][blueY];
			array[blueX][blueY] = array[bX][bY];
			array[bX][bY] = temp;
			temp = array[redX][redY];
			array[redX][redY] = array[rX][rY];
			array[rX][rY] = temp;
			count++;
		} else {
			blueX = bX;
			blueY = bY;
			redX = rX;
			redY = rY;
		}
		
		for(int i = 0; i < 4; i++) {
			if(i == index) continue;
			
			bfs(array, i, count, blueX, blueY, redX, redY);
		}
	}
}

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.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, M; // N 세로, M 가로
	static int[] dirx = { -1, 0, 1, 0 };
	static int[] diry = { 0, -1, 0, 1 };
	static char map[][];

	static boolean[][][][] visit;

	static Queue<Node> queue = new LinkedList<Node>();

	public static void main(String[] args) throws Exception {

		InputStreamReader ir = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(ir);

		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new char[M][N];
		visit = new boolean[M][N][M][N];

		Node initNode = new Node(0, 0, 0, 0, 0);

		for (int n = 0; n < N; n++) {
			String token = br.readLine();
			for (int m = 0; m < M; m++) {
				char tmp = token.charAt(m);
				map[m][n] = tmp;
				if (tmp == 'R') {
					initNode.rx = m;
					initNode.ry = n;
				}
				if (tmp == 'B') {
					initNode.bx = m;
					initNode.by = n;
				}
			}
		}

		queue.offer(initNode);

		while (!queue.isEmpty()) {
			Node node = queue.poll();

			visit[node.rx][node.ry][node.bx][node.by] = true;

			if (node.count >= 10)
			{
				continue;
			}

			for (int i = 0; i < 4; i++) {
				int bx = node.bx;
				int by = node.by;
				int rx = node.rx;
				int ry = node.ry;
				// 파란색 구슬부터 굴림.
				while (map[bx + dirx[i]][by + diry[i]] != '#') {
					bx += dirx[i];
					by += diry[i];
					if (map[bx][by] == 'O')
						break;
				}

				if (map[bx][by] == 'O')
					continue;

				while (map[rx + dirx[i]][ry + diry[i]] != '#') {
					rx += dirx[i];
					ry += diry[i];
					if (map[rx][ry] == 'O')
						break;
				}

				if (map[rx][ry] == 'O') {
					System.out.println(node.count + 1);
					return;
				}

				// 겹치는 경우 처리
				if (bx == rx && by == ry) {
					switch (i) {
					case 0:
						if (node.bx > node.rx) {
							bx += 1;
						} else
							rx += 1;
						break;
					case 1:
						if (node.by > node.ry) {
							by += 1;
						} else
							ry += 1;
						break;
					case 2:
						if (node.bx > node.rx) {
							rx -= 1;
						} else
							bx -= 1;
						break;
					case 3:
						if (node.by > node.ry) {
							ry -= 1;
						} else
							by -= 1;
						break;
					}
				}

				if (!visit[rx][ry][bx][by]) {
					queue.offer(new Node(rx, ry, bx, by, node.count + 1));
				}
			}
		}
		System.out.println(-1);
	}
}

class Node {
	public int rx;
	public int ry;
	public int bx;
	public int by;
	public int count;

	public Node() {
	}

	public Node(int rx, int ry, int bx, int by, int count) {
		this.rx = rx;
		this.ry = ry;
		this.bx = bx;
		this.by = by;
		this.count = count;
	}
}

 

 

17144번: 미세먼지 안녕!

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사

www.acmicpc.net

 

 

 

 


 

 

  • 내용

공기청정기(1열에 2칸을 차지하고있음)랑 A(r,c)위치에 미세먼지 양이 적혀있다.

 

A(r,c)에 있는 미세먼지 양은 턴 한번마다 네방향(상, 하, 좌, 우)로 퍼질 수 있고 퍼지는 양은 A(r,c)/5만큼 퍼진다.(소수점 버림) 퍼진 뒤 A(r,c)의 미세먼지 양은 A(r,c) - A(r,c)/5 X (퍼진방향수)로 바뀐다.

공기청정기는 위에 2칸이 있다고 있는데 위칸은 시계 반대방향으로 불고, 아래칸은 시계 방향으로 분다.

 

한 턴마다 미세먼지가 먼저 퍼지고 공기청정기의 바람이 분다.

이때, T턴 후 남아있는 미세먼지의 양을 출력한다.

 

 

 

  • 생각

 

T초마다 미세먼지 퍼뜨리고 공기청정기 돌리면 된다. (딱히 문법 사용할거 없이 구현하면 될 것 같다.)

 

미세먼지 양은 네 방향으로 퍼뜨려도 총 미세먼지의 양은 변화가 없다. (공기청정기가 불어서 미세먼지가 줄어드는 2칸만 총양에서 빼주면 됨.)

 

 

 

  • 코드

 

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

public class Main {
	static int[] x = { -1, 1, 0, 0 };
	static int[] y = { 0, 0, -1, 1 };
	static int[][] array, temp;
	static int r, c, answer, airCleaner1, airCleaner2;

	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);

		answer = 2;
		r = in.nextInt();
		c = in.nextInt();
		int testcase = in.nextInt();
		array = new int[r][c];
		temp = new int[r][c];
		
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				array[i][j] = in.nextInt();
				answer += array[i][j];
				if (array[i][j] < 0) {
					if (airCleaner1 == 0) {
						airCleaner1 = i;
					} else {
						airCleaner2 = i;
					}
				}

			}
		}

		while (testcase-- > 0) {
			SpreadFineDust();
			PlayAirCleaner();
			CopyMap(temp, array);
		}
	}

	private static void SpreadFineDust() {
		for(int i = 0; i < r; i++)
			Arrays.fill(temp[i], 0);
		
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				temp[i][j] += array[i][j];

				if(temp[i][j] == -1) continue;
				if(array[i][j] == 0) continue;
				
				for (int direction = 0; direction < 4; direction++) {
					int R = i + x[direction];
					int C = j + y[direction];

					if (R < 0 || C < 0 || R >= r || C >= c)	continue;
					if (array[R][C] == -1)	continue;

					temp[R][C] += (array[i][j] / 5);
					temp[i][j] -= (array[i][j] / 5);
				}
			}
		}
	}

	private static void PlayAirCleaner() {
		// 위쪽 공기청정기는 반시계방향
		int top = airCleaner1;

		answer -= temp[top-1][0];
		for (int x = top - 1; x > 0; x--) {
			temp[x][0] = temp[x - 1][0];
		}

		for (int y = 0; y < c - 1; y++) {
			temp[0][y] = temp[0][y + 1];
		}

		for (int x = 0; x < top; x++) {
			temp[x][c - 1] = temp[x + 1][c - 1];
		}

		for (int y = c - 1; y > 1; y--) {
			temp[top][y] = temp[top][y - 1];
		}

		temp[top][1] = 0;

		// 아래쪽 공기청정기는 시계 방향
		int bottom = airCleaner2;

		answer -= temp[bottom + 1][0];
		for (int x = bottom + 1; x < r - 1; x++) {
			temp[x][0] = temp[x + 1][0];
		}

		for (int y = 0; y < c - 1; y++) {
			temp[r - 1][y] = temp[r - 1][y + 1];
		}

		for (int x = r - 1; x > bottom; x--) {
			temp[x][c - 1] = temp[x - 1][c - 1];
		}

		for (int y = c - 1; y > 1; y--) {
			temp[bottom][y] = temp[bottom][y - 1];
		}

		temp[bottom][1] = 0;
	}
	
	static void CopyMap(int[][] one,int[][] two) {
		for(int i=0;i<one.length;++i) {
			System.arraycopy(one[i], 0, two[i], 0, two[i].length);
		}
	}
}

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;
	}
}

+ Recent posts