AMUSEMENTPARK 놀이 공원 / algospot.com

문제링크 : 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();
        }
    }
}