๊ธฐ๋ก๋ฐฉ

BOJ_17143 : ๋‚š์‹œ์™• ๋ณธ๋ฌธ

CodingTest/Java

BOJ_17143 : ๋‚š์‹œ์™•

Soom_1n 2023. 4. 7. 17:20

๐Ÿ‘‰ ๋ฌธ์ œ๋งํฌ

 

17143๋ฒˆ: ๋‚š์‹œ์™•

๋‚š์‹œ์™•์ด ์ƒ์–ด ๋‚š์‹œ๋ฅผ ํ•˜๋Š” ๊ณณ์€ ํฌ๊ธฐ๊ฐ€ R×C์ธ ๊ฒฉ์žํŒ์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค. ๊ฒฉ์žํŒ์˜ ๊ฐ ์นธ์€ (r, c)๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค. r์€ ํ–‰, c๋Š” ์—ด์ด๊ณ , (R, C)๋Š” ์•„๋ž˜ ๊ทธ๋ฆผ์—์„œ ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ ์•„๋ž˜์— ์žˆ๋Š” ์นธ์ด๋‹ค.

www.acmicpc.net


< ์˜ˆ์ œ ์ƒ๋žต >


๐Ÿ”ธ ๋ฌธ์ œ ๋ถ„์„ ๐Ÿ”ธ

  • R x C ๊ฒฉ์žํŒ์— M๋งˆ๋ฆฌ์˜ ์ƒ์–ด๊ฐ€ ์žˆ๋‹ค.
    • 1์ดˆ์— ๋‚š์‹œ์™•์ด ์˜ค๋ฅธ์ชฝ์œผ๋กœ ํ•œ ์นธ ์ด๋™ํ•˜๊ณ , ์ƒ์–ด๋“ค์€ ์†๋„ ๋งŒํผ ์ด๋™ํ•œ๋‹ค.
      • ๋‚š์‹œ์™•์ด ์ด๋™ ํ–ˆ์„ ๋•Œ ๊ฐ™์€ ์—ด์˜ ๊ฐ€์žฅ ์œ„์ชฝ์— ์žˆ๋Š” ์ƒ์–ด๋ฅผ ์žก๋Š”๋‹ค.
      • ์ƒ์–ด๊ฐ€ ๊ฒน์น˜๋ฉด ํฌ๊ธฐ๊ฐ€ ํฐ ์ƒ์–ด๊ฐ€ ๋‹ค ์žก์•„๋จน๊ณ  ํ˜ผ์ž ๋‚จ๋Š”๋‹ค.
      • ์ƒ์–ด๊ฐ€ ์ด๋™ํ•  ๋•Œ ๋ฒฝ์— ๋ถ€๋”›ํžˆ๋ฉด ๋ฐ˜๋Œ€ ๋ฐฉํ–ฅ์œผ๋กœ ๋งˆ์ € ์ด๋™ํ•œ๋‹ค.
    • ๋‚š์‹œ์™•์ด ๋๊นŒ์ง€ ์ด๋™ํ–ˆ์„ ๋•Œ ์žก์€ ์ƒ์–ด ํฌ๊ธฐ์˜ ํ•ฉ์„ ์ถœ๋ ฅํ•œ๋‹ค.
  • ๋‚š์‹œ์™• ์ด๋™ ํ›„ ์ƒ์–ด๋“ค์˜ ์›€์ง์ž„์„ ์ˆœ์„œ๋Œ€๋กœ ๊ตฌํ˜„ํ•œ๋‹ค.

๐Ÿ”ธ ์ฝ”๋“œ ๐Ÿ”ธ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static class Shark {
        int s, d, z;

        public Shark(int s, int d, int z) {
            this.s = s;
            this.d = d;
            this.z = z;
        }
    }

    private static int R, C, M, ans;
    private static Shark[][] map, temp;
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new Shark[R + 1][C + 1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            map[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = new Shark(
                    Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) - 1,
                    Integer.parseInt(st.nextToken()));
        }

        // ๋‚š์‹œ์™• ์ด๋™
        for (int i = 1; i <= C; i++) {
            // ์ƒ์–ด ์žˆ์œผ๋ฉด ์žก๊ธฐ
            for (int j = 1; j <= R; j++) {
                if (map[j][i] != null) {
                    ans += map[j][i].z;
                    M--;
                    map[j][i] = null;
                    break;
                }
            }

            // ์ƒ์–ด ์ด๋™
            temp = new Shark[R + 1][C + 1];
            for (int j = 1; j <= R; j++) {
                for (int k = 1; k <= C; k++) {
                    if (map[j][k] != null) { // ์ƒ์–ด ๋ฐœ๊ฒฌ
                        move_shark(j, k, map[j][k]); // ์ด๋™
                    }
                }
            }
            deepCopy();
        }
        System.out.println(ans);
    }

    private static void move_shark(int r, int c, Shark shark) {
        // ์ƒ์–ด ์ด๋™
        int dd = shark.d % 2 == 0 ? 1 : -1;
        int dr = r, dc = c;
        for (int i = 0; i < shark.s; i++) {
            dr = r + dx[shark.d];
            dc = c + dy[shark.d];
            if (1 > dr || dr > R || 1 > dc || dc > C) {
                shark.d += dd;
                dd *= -1;
                i--;
                continue;
            }
            r = dr;
            c = dc;
        }

        // ์ƒ์–ด ์œ„์น˜ ์ €์žฅ
        if (temp[dr][dc] == null) {
            temp[dr][dc] = shark;
        } else {
            temp[dr][dc] = temp[dr][dc].z > shark.z ? temp[dr][dc] : shark;
        }
    }

    private static void deepCopy() {
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                if (temp[i][j] != null)
                    map[i][j] = temp[i][j];
                else {
                    map[i][j] = null;
                }
            }
        }
    }
    private static void print() {
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                if (map[i][j] != null) {
                    System.out.print('S' + " ");
                } else {
                    System.out.print('O' + " ");
                }
            }
            System.out.println();
        }
    }
}

๐Ÿ”ธ ์ฝ”๋“œ ํ•ด์„ ๐Ÿ”ธ

  • ๋‚š์‹œ์™•์ด 1๋ถ€ํ„ฐ C๊นŒ์ง€ ์ด๋™ํ•œ๋‹ค.
    • ๊ฐ™์€ ์—ด์— ์ƒ์–ด๊ฐ€ ์žˆ๋‹ค๋ฉด, ๊ฐ€์žฅ ์œ„์— ์žˆ๋Š” ์ƒ์–ด๋ฅผ ์žก๊ณ  ์นด์šดํŠธ ํ•œ๋‹ค.
    • ์ƒ์–ด๊ฐ€ ์ด๋™ํ•œ๋‹ค.
      • map์—์„œ ์ƒ์–ด๋ฅผ ๋ฐœ๊ฒฌํ•˜๋ฉด move_shark ๋ฉ”์„œ๋“œ์—์„œ ์ด๋™ ํ›„ temp์— ์ €์žฅํ•œ๋‹ค.
        • ์ƒ์–ด์˜ ์†๋„ ๋งŒํผ ์ด๋™ํ•˜๋Š”๋ฐ ๋ฒฝ์— ๋ถ€๋”›ํžˆ๋ฉด ๋ฐ˜๋Œ€ ๋ฐฉํ–ฅ์œผ๋กœ ๋งˆ์ € ์ด๋™ํ•œ๋‹ค.
        • ์ง์ˆ˜ ๋ฐฉํ–ฅ์ด๋ผ๋ฉด +1, ํ™€์ˆ˜ ๋ฐฉํ–ฅ์ด๋ผ๋ฉด -1์„ ํ•˜๋ฉด ๋ฐ˜๋Œ€ ๋ฐฉํ–ฅ์ด ๋œ๋‹ค.
        • ์ƒ์–ด์˜ ์œ„์น˜๋ฅผ temp์— ์ €์žฅ ํ•  ๋•Œ ํฌ๊ธฐ๊ฐ€ ํฐ ์ƒ์–ด๋งŒ ๋‚จ๊ธด๋‹ค.
      • temp๋ฅผ map์œผ๋กœ ๋ณต์‚ฌํ•ด map ์ •๋ณด๋ฅผ ์—…๋ฐ์ดํŠธํ•œ๋‹ค.
  • ๋‚š์‹œ์™•์ด ์ด๋™ํ•˜๋ฉฐ ์žก์€ ์ƒ์–ด์˜ ํฌ๊ธฐ์˜ ํ•ฉ์„ ์ถœ๋ ฅํ•œ๋‹ค.

๐Ÿ”ธ end ๐Ÿ”ธ

  • ๋ฐ˜๋Œ€๋ฐฉํ–ฅ์„ if๋ฌธ์œผ๋กœ ํŒ๋‹จํ•˜๊ธฐ๋ณด๋‹ค, %์—ฐ์‚ฐ์„ ์ด์šฉํ•˜๋Š”๊ฒŒ ์˜ค๋ฒ„ํ—ค๋“œ๊ฐ€ ๋” ๋‚ฎ์•˜์„ ๊ฒƒ ๊ฐ™๋‹ค.

728x90