ALGOSPOT
AMUSEMENTPARK 놀이 공원 / algospot.com
건이두
2020. 1. 28. 18:38
728x90
문제링크 : https://algospot.com/judge/problem/read/AMUSEMENTPARK
제출링크 : CPP 코드로 제출한 링크 https://algospot.com/judge/submission/detail/653294
CPP 소스 : https://github.com/skysign/WSAPT/blob/master/algospot.com/AMUSEMENTPARK_cpp/AMUSEMENTPARK/AMUSEMENTPARK.cpp
자바 소스 : https://github.com/skysign/WSAPT/blob/master/algospot.com/AMUSEMENTPARK_java/src/Main.java
정확한 이유는 잘 모르겠지만, 자바코드로 작성해서 올리면, '시간초과'로 정답 처리가 되지 않습니다.
맞게 코딩한 것 같은대, 계속 정답처리가 안되서, 같은 방식으로 cpp로 코딩했더니,
정답 처리가 되네요. cpp 코드는 AMUSEMENTPARK_cpp 폴더 참고하세요.
오렌지가 멜론을 볼 수 있는 회수와 볼 수 있는 위치를 알아내는 문제입니다.
두친구가 이동하는 경로는 동일하지만, 시작하는 위치가 서로 다릅니다.
이동할 위치를 먼저 저장하는 코드를 작성해보겠습니다.
int[] posIs = new int[M*N+1];
int[] posJs = new int[M*N+1];
int cntPos = 0;
for(int i=0; i<M; ++i) {
for(int j=0; j<N; ++j) {
mMap[i][j] = sc.nextInt();
if(mMap[i][j] > 0) {
posIs[mMap[i][j]] = i;
posJs[mMap[i][j]] = j;
cntPos++;
}
}
}이중루프를 한번만 사용하면서, 동시에 지도를 입력받고, 이동경로도 저장하는 것이 중요한 포인트입니다.
이후에 for( ; i<=cntPos; ) 이와 같은 루프를 사용해서, 오렌지와 멜론이 이동하는 것을 코딩할 수 있습니다.
바로 옆에 있으면 보인다
오렌지와 멜론이 바로 옆에 있으면, 중간에 가로 막을 수 있는 것이 없으므로, 항상 볼 수 있습니다.
멜론을 기준으로, 오렌지가 옆에 있는지
public boolean AreTheyAdjacent(int Oi, int Oj, int Mi, int Mj) {
int[] di = new int[]{-1, 1, 0, 0, -1, -1, 1, 1};
int[] dj = new int[]{0, 0, -1, 1, -1, 1, 1, -1};
for(int k=0; k<di.length; ++k) {
if((Oi == (Mi + di[k])) && (Oj == (Mj + dj[k])))
return true;
}
return false;
}같은 행 또는 열에 있는 경우
오렌지와 멜론의 i 또는 j값이 동일 합니다. 중간이 모두 비어 있으면 볼 수 있습니다.
// i 가 같음
if(Oi == Mi) {
int fixedI = Oi;
int begJ = Math.min(Oj, Mj) +1;
int endJ = Math.max(Oj, Mj);
for(int j = begJ; j < endJ; ++j) {
if(mMap[fixedI][j] != 0) {
return true;
}
}
return false;
}
// j 가 같음
if(Oj == Mj) {
int fixedJ = Oj;
int begI = Math.min(Oi, Mi) +1;
int endI = Math.max(Oi, Mi);
for(int i = begI; i < endI; ++i) {
if(mMap[i][fixedJ] != 0) {
return true;
}
}
return false;
}대각선에 있는 경우? 중간이 막혔을까? 아닐까?
이문제 가장 중요한 부분으로 생각합니다. 대각선에 오렌지와 멜론이 위치할 때, 오렌지가 멜론을 볼 수 있는지 여부를 구현하는 부분입니다.
di와 dj를 계산하고, 두 숫자가 모두 소수이면, 중간에 막을 수 있는 위치가 없습니다.
int di = Math.abs(Oi - Mi);
int dj = Math.abs(Oj - Mj);
// di와 dj 가 둘다 소수이면
// 중간에 시선을 막는 부분이 존재 하지 않음
if(AreTheyPrimeNumber(di, dj))
return false;
public boolean AreTheyPrimeNumber(int a, int b) {
int min = Math.min(a, b);
for(int i=2; i<=min; ++i) {
if ((a%i == 0) && (b%i == 0)) {
return false;
}
}
return true;
}우선 문제에 나와 있는대로, 오렌지(0,0) 멜론(2,2)의 경우를 생각해 보면, (1,1)이 0이면 볼 수 있고, 다른 숫자이면 볼 수 없습니다.
여기서 한가지 더 생각해야 할 경우가 있습니다.
오렌지(0,0) 멜론(3,6) 이런 경우에 오렌지가 멜론을 볼 수 있으려면,
중간에 2개의 위치(1,2) 와 (2,4)가 0 이어야 볼 수 있습니다.
오렌지가 멜론에게 다가간다고 생각하고, 중간에 막고있는 블럭이 모두 0인지 확인해 보는 코드입니다.
int gcd = gcd(di, dj);
di = (Mi - Oi) / gcd;
dj = (Mj - Oj) / gcd;
for(int step=1, i = Oi, j = Oj; step<gcd; ++step) {
i += di;
j += dj;
if(mMap[i][j] != 0)
return true;
}전체 소스코드는 아래와 같습니다.
import java.io.*;
import java.util.ArrayList;
import java.util.Scanner;
/**
* AMUSEMENTPARK 놀이 공원 / algospot.com
* 문제링크 : https://algospot.com/judge/problem/read/AMUSEMENTPARK
* 제출링크 : CPP 코드 https://algospot.com/judge/submission/detail/653294
*
* 정확한 이유는 잘 모르겠지만, 자바코드로 작성해서 올리면, '시간초과'로 정답 처리가 되지 않습니다.
* 맞게 코딩한 것 같은대, 계속 정답처리가 안되서, 같은 방식으로 cpp로 코딩했더니,
* 정답 처리가 되네요. cpp 코드는 AMUSEMENTPARK_cpp 폴더 참고하세요.
*/
public class Main {
int[][] mMap;
public void solve() throws IOException {
// Scanner sc = new Scanner(System.in);
Reader sc = new Reader();
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int M = sc.nextInt();
int N = sc.nextInt();
int MelonPos = sc.nextInt();
mMap = new int[M][N];
// 정답 저장
ArrayList<Integer> mR = new ArrayList();
int[] posIs = new int[M*N+1];
int[] posJs = new int[M*N+1];
int cntPos = 0;
for(int i=0; i<M; ++i) {
for(int j=0; j<N; ++j) {
mMap[i][j] = sc.nextInt();
if(mMap[i][j] > 0) {
posIs[mMap[i][j]] = i;
posJs[mMap[i][j]] = j;
cntPos++;
}
}
}
for(int mPos=MelonPos, oPos=1; mPos<=cntPos; ++mPos, ++oPos) {
if(true == AreTheyAdjacent(posIs[oPos], posJs[oPos], posIs[mPos], posJs[mPos])) {
mR.add(oPos);
}
else if(false == AreTheyBlocked(posIs[oPos], posJs[oPos], posIs[mPos], posJs[mPos])) {
mR.add(oPos);
}
}
bw.write(mR.size()+"\n");
for(int r : mR) {
bw.write(r+"\n");
}
bw.close();
}
public boolean AreTheyAdjacent(int Oi, int Oj, int Mi, int Mj) {
int[] di = new int[]{-1, 1, 0, 0, -1, -1, 1, 1};
int[] dj = new int[]{0, 0, -1, 1, -1, 1, 1, -1};
for(int k=0; k<di.length; ++k) {
if((Oi == (Mi + di[k])) && (Oj == (Mj + dj[k])))
return true;
}
return false;
}
public boolean AreTheyBlocked(int Oi, int Oj, int Mi, int Mj) {
// i 가 같음
if(Oi == Mi) {
int fixedI = Oi;
int begJ = Math.min(Oj, Mj) +1;
int endJ = Math.max(Oj, Mj);
for(int j = begJ; j < endJ; ++j) {
if(mMap[fixedI][j] != 0) {
return true;
}
}
return false;
}
// j 가 같음
if(Oj == Mj) {
int fixedJ = Oj;
int begI = Math.min(Oi, Mi) +1;
int endI = Math.max(Oi, Mi);
for(int i = begI; i < endI; ++i) {
if(mMap[i][fixedJ] != 0) {
return true;
}
}
return false;
}
int di = Math.abs(Oi - Mi);
int dj = Math.abs(Oj - Mj);
// di와 dj 가 둘다 소수이면
// 중간에 시선을 막는 부분이 존재 하지 않음
if(AreTheyPrimeNumber(di, dj))
return false;
// Orange와 Melon이 대각선 방향에 있음
// Orange에서 Melon방향으로 다가갈 때,
// 중간이 막혀 있으면 blocked(true)
int gcd = gcd(di, dj);
di = (Mi - Oi) / gcd;
dj = (Mj - Oj) / gcd;
for(int step=1, i = Oi, j = Oj; step<gcd; ++step) {
i += di;
j += dj;
if(mMap[i][j] != 0)
return true;
}
return false;
}
public boolean AreTheyPrimeNumber(int a, int b) {
int min = Math.min(a, b);
for(int i=2; i<=min; ++i) {
if ((a%i == 0) && (b%i == 0)) {
return false;
}
}
return true;
}
public int gcd(int a,int b) {
if(b==0)
return a;
return gcd(b, a%b);
}
public static void main(String[] args) throws IOException {
Main main = new Main();
main.solve();
}
// https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/
static class Reader
{
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader()
{
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public Reader(String file_name) throws IOException
{
din = new DataInputStream(new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public String nextLine() throws IOException
{
byte[] buf = new byte[64]; // line length
int cnt = 0, c;
while ((c = read()) != -1)
{
if (c == '\n')
break;
buf[cnt++] = (byte) c;
}
return new String(buf, 0, cnt);
}
public int nextInt() throws IOException
{
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do
{
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public long nextLong() throws IOException
{
long ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
}
while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public double nextDouble() throws IOException
{
double ret = 0, div = 1;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
}
while ((c = read()) >= '0' && c <= '9');
if (c == '.')
{
while ((c = read()) >= '0' && c <= '9')
{
ret += (c - '0') / (div *= 10);
}
}
if (neg)
return -ret;
return ret;
}
private void fillBuffer() throws IOException
{
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException
{
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException
{
if (din == null)
return;
din.close();
}
}
}
728x90