๋ฌธ์ œ ์„ค๋ช…


๐Ÿ’ก Info

๋‚ด์šฉ

NxN ํฌ๊ธฐ์˜ ๋ณต๋„๊ฐ€ ์žˆ๋‹ค. ๋ณต๋„๋Š” 1x1 ํฌ๊ธฐ์˜ ์นธ์œผ๋กœ ๋‚˜๋ˆ„์–ด์ง€๋ฉฐ, ํŠน์ •ํ•œ ์œ„์น˜์—๋Š” ์„ ์ƒ๋‹˜, ํ•™์ƒ, ํ˜น์€ ์žฅ์• ๋ฌผ์ด ์œ„์น˜ํ•  ์ˆ˜ ์žˆ๋‹ค. ํ˜„์žฌ ๋ช‡ ๋ช…์˜ ํ•™์ƒ๋“ค์€ ์ˆ˜์—…์‹œ๊ฐ„์— ๋ชฐ๋ž˜ ๋ณต๋„๋กœ ๋น ์ ธ๋‚˜์™”๋Š”๋ฐ, ๋ณต๋„๋กœ ๋น ์ ธ๋‚˜์˜จ ํ•™์ƒ๋“ค์€ ์„ ์ƒ๋‹˜์˜ ๊ฐ์‹œ์— ๋“คํ‚ค์ง€ ์•Š๋Š” ๊ฒƒ์ด ๋ชฉํ‘œ์ด๋‹ค.

๊ฐ ์„ ์ƒ๋‹˜๋“ค์€ ์ž์‹ ์˜ ์œ„์น˜์—์„œ ์ƒ, ํ•˜, ์ขŒ, ์šฐ 4๊ฐ€์ง€ ๋ฐฉํ–ฅ์œผ๋กœ ๊ฐ์‹œ๋ฅผ ์ง„ํ–‰ํ•œ๋‹ค. ๋‹จ, ๋ณต๋„์— ์žฅ์• ๋ฌผ์ด ์œ„์น˜ํ•œ ๊ฒฝ์šฐ, ์„ ์ƒ๋‹˜์€ ์žฅ์• ๋ฌผ ๋’คํŽธ์— ์ˆจ์–ด ์žˆ๋Š” ํ•™์ƒ๋“ค์€ ๋ณผ ์ˆ˜ ์—†๋‹ค. ๋˜ํ•œ ์„ ์ƒ๋‹˜์€ ์ƒ, ํ•˜, ์ขŒ, ์šฐ 4๊ฐ€์ง€ ๋ฐฉํ–ฅ์— ๋Œ€ํ•˜์—ฌ, ์•„๋ฌด๋ฆฌ ๋ฉ€๋ฆฌ ์žˆ๋”๋ผ๋„ ์žฅ์• ๋ฌผ๋กœ ๋ง‰ํžˆ๊ธฐ ์ „๊นŒ์ง€์˜ ํ•™์ƒ๋“ค์€ ๋ชจ๋‘ ๋ณผ ์ˆ˜ ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•˜์ž.

๋‹ค์Œ๊ณผ ๊ฐ™์ด 3x3 ํฌ๊ธฐ์˜ ๋ณต๋„์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง„ ์ƒํ™ฉ์„ ํ™•์ธํ•ด๋ณด์ž. ๋ณธ ๋ฌธ์ œ์—์„œ ์œ„์น˜ ๊ฐ’์„ ๋‚˜ํƒ€๋‚ผ ๋•Œ๋Š” (ํ–‰,์—ด)์˜ ํ˜•ํƒœ๋กœ ํ‘œํ˜„ํ•œ๋‹ค. ์„ ์ƒ๋‹˜์ด ์กด์žฌํ•˜๋Š” ์นธ์€ T, ํ•™์ƒ์ด ์กด์žฌํ•˜๋Š” ์นธ์€ S, ์žฅ์• ๋ฌผ์ด ์กด์žฌํ•˜๋Š” ์นธ์€ O๋กœ ํ‘œ์‹œํ•˜์˜€๋‹ค. ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด (3,1)์˜ ์œ„์น˜์—๋Š” ์„ ์ƒ๋‹˜์ด ์กด์žฌํ•˜๋ฉฐ (1,1), (2,1), (3,3)์˜ ์œ„์น˜์—๋Š” ํ•™์ƒ์ด ์กด์žฌํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  (1,2), (2,2), (3,2)์˜ ์œ„์น˜์—๋Š” ์žฅ์• ๋ฌผ์ด ์กด์žฌํ•œ๋‹ค.

์ด ๋•Œ (3,3)์˜ ์œ„์น˜์— ์กด์žฌํ•˜๋Š” ํ•™์ƒ์€ ์žฅ์• ๋ฌผ ๋’คํŽธ์— ์ˆจ์–ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ๊ฐ์‹œ๋ฅผ ํ”ผํ•  ์ˆ˜ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ (1,1)๊ณผ (2,1)์˜ ์œ„์น˜์— ์กด์žฌํ•˜๋Š” ํ•™์ƒ์€ ์„ ์ƒ๋‹˜์—๊ฒŒ ๋“คํ‚ค๊ฒŒ ๋œ๋‹ค.

ํ•™์ƒ๋“ค์€ ๋ณต๋„์˜ ๋นˆ ์นธ ์ค‘์—์„œ ์žฅ์• ๋ฌผ์„ ์„ค์น˜ํ•  ์œ„์น˜๋ฅผ ๊ณจ๋ผ, ์ •ํ™•ํžˆ 3๊ฐœ์˜ ์žฅ์• ๋ฌผ์„ ์„ค์น˜ํ•ด์•ผ ํ•œ๋‹ค. ๊ฒฐ๊ณผ์ ์œผ๋กœ 3๊ฐœ์˜ ์žฅ์• ๋ฌผ์„ ์„ค์น˜ํ•˜์—ฌ ๋ชจ๋“  ํ•™์ƒ๋“ค์„ ๊ฐ์‹œ๋กœ๋ถ€ํ„ฐ ํ”ผํ•˜๋„๋ก ํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ๊ณ„์‚ฐํ•˜๊ณ ์ž ํ•œ๋‹ค. NxN ํฌ๊ธฐ์˜ ๋ณต๋„์—์„œ ํ•™์ƒ ๋ฐ ์„ ์ƒ๋‹˜์˜ ์œ„์น˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์žฅ์• ๋ฌผ์„ ์ •ํ™•ํžˆ 3๊ฐœ ์„ค์น˜ํ•˜์—ฌ ๋ชจ๋“  ํ•™์ƒ๋“ค์ด ์„ ์ƒ๋‹˜๋“ค์˜ ๊ฐ์‹œ๋ฅผ ํ”ผํ•˜๋„๋ก ํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์˜ˆ๋ฅผ ๋“ค์–ด N=5์ผ ๋•Œ, ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์„ ์ƒ๋‹˜ ๋ฐ ํ•™์ƒ์˜ ์œ„์น˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์กŒ๋‹ค๊ณ  ๊ฐ€์ •ํ•˜์ž.

์ด ๋•Œ ๋‹ค์Œ๊ณผ ๊ฐ™์ด 3๊ฐœ์˜ ์žฅ์• ๋ฌผ์„ ์„ค์น˜ํ•˜๋ฉด, ๋ชจ๋“  ํ•™์ƒ๋“ค์„ ์„ ์ƒ๋‹˜์˜ ๊ฐ์‹œ๋กœ๋ถ€ํ„ฐ ํ”ผํ•˜๋„๋ก ๋งŒ๋“ค ์ˆ˜ ์žˆ๋‹ค.

๐Ÿ“ฅ์ž…๋ ฅ ์กฐ๊ฑด

  • ์ฒซ์งธ ์ค„์— ์ž์—ฐ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. (3 โ‰ค N โ‰ค 6)
  • ๋‘˜์งธ ์ค„์— N๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ์„œ ๋ณต๋„์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.
  • ๊ฐ ํ–‰์—์„œ๋Š” N๊ฐœ์˜ ์›์†Œ๊ฐ€ ๊ณต๋ฐฑ์„ ๊ธฐ์ค€์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด ์ฃผ์–ด์ง„๋‹ค.
  • ํ•ด๋‹น ์œ„์น˜์— ํ•™์ƒ์ด ์žˆ๋‹ค๋ฉด S, ์„ ์ƒ๋‹˜์ด ์žˆ๋‹ค๋ฉด T, ์•„๋ฌด๊ฒƒ๋„ ์กด์žฌํ•˜์ง€ ์•Š๋Š”๋‹ค๋ฉด X๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.
  • ๋‹จ, ์ „์ฒด ์„ ์ƒ๋‹˜์˜ ์ˆ˜๋Š” 5์ดํ•˜์˜ ์ž์—ฐ์ˆ˜, ์ „์ฒด ํ•™์ƒ์˜ ์ˆ˜๋Š” 30์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋ฉฐ ํ•ญ์ƒ ๋นˆ ์นธ์˜ ๊ฐœ์ˆ˜๋Š” 3๊ฐœ ์ด์ƒ์œผ๋กœ ์ฃผ์–ด์ง„๋‹ค.
//์˜ˆ1
5
X S X X T
T X S X X
X X X X X
X T X X X
X X T X X
//์˜ˆ2
4
S S S T
X X X X
X X X X
T T T X

๐Ÿ“ค์ถœ๋ ฅ ์กฐ๊ฑด

  • ์ฒซ์งธ ์ค„์— ์ •ํ™•ํžˆ 3๊ฐœ์˜ ์žฅ์• ๋ฌผ์„ ์„ค์น˜ํ•˜์—ฌ ๋ชจ๋“  ํ•™์ƒ๋“ค์„ ๊ฐ์‹œ๋กœ๋ถ€ํ„ฐ ํ”ผํ•˜๋„๋ก ํ•  ์ˆ˜ ์žˆ๋Š”์ง€์˜ ์—ฌ๋ถ€๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.
  • ๋ชจ๋“  ํ•™์ƒ๋“ค์„ ๊ฐ์‹œ๋กœ๋ถ€ํ„ฐ ํ”ผํ•˜๋„๋ก ํ•  ์ˆ˜ ์žˆ๋‹ค๋ฉด "YES", ๊ทธ๋ ‡์ง€ ์•Š๋‹ค๋ฉด "NO"๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.
//์˜ˆ1
YES
//์˜ˆ2
NO


๋ฌธ์ œ ์ดํ•ด


  • N X N ํฌ๊ธฐ์˜ ๋ณต๋„์—์„œ ํ•™์ƒ๊ณผ ์„ ์ƒ๋‹˜์˜ ์œ„์น˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์žฅ์• ๋ฌผ์„ ์ •ํ™•ํžˆ 3๊ฐœ ์„ค์น˜ํ•˜์—ฌ ๋ชจ๋“  ํ•™์ƒ์ด ์„ ์ƒ๋‹˜์˜ ๊ฐ์‹œ๋ฅผ ํ”ผํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ


์•Œ๊ณ ๋ฆฌ์ฆ˜


์‹ค์ œ ํ’€์ด ์‹œ๊ฐ„ : 50๋ถ„

  • ์ž…๋ ฅ

    • ์ „์—ญ๋ณ€์ˆ˜ ์„ ์–ธ: N, arr, dx, dy, result
    • N ์ž…๋ ฅ๋ฐ›๊ธฐ
    • ๋ฐฐ์—ด arr ์ž…๋ ฅ๋ฐ›๊ธฐ
  • ๊ณ„์‚ฐ

    • BFS ์‹คํ–‰ํ•˜๊ธฐ
  • ์ถœ๋ ฅ

    • ๋งŒ์•ฝ ์›ํ•˜๋Š” ๊ฒฐ๊ณผ -> YES ์ถœ๋ ฅ
    • ๊ทธ๋ ‡์ง€ ์•Š๋‹ค๋ฉด -> NO ์ถœ๋ ฅ
  • ๋ณ„๋„ ๋ฉ”์„œ๋“œ

    • BFS
      • ํ ์ƒ์„ฑ
        • ๊ณต๊ฐ„ ๋ฐ–์œผ๋กœ ๋‚˜๊ฐˆ ๊ฒฝ์šฐ -> ๋ฌด์‹œ
        • ์žฅ์• ๋ฌผ ์„ค์น˜
      • ๋นˆ ๊ณต๊ฐ„ ํ™•์ธ
import java.util.*;

public class Main {

    static int N;
    static int[][] arr;

    static int[] dx = {-1, 1, 0 ,0};
    static int[] dy = {0, 0, -1, 1};
    static boolean result;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        
        sc.nextLine();

        arr = new int[N][N];
        for(int i=0; i<N; i++){
            String map = sc.nextLine();
            for(int j=0; j<N; j++){
                arr[i][j] = map.charAt(0) - '0';
            }
        }

        result = bfs();

        if(result == true){
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }

    public static boolean bfs(){
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                }
            }
        }

        while(!queue.isEmpty()){
            int[] now = queue.poll();
            int x = now[0];
            int y = now[1];

            for(int i=0; i<4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx < 0 || ny < 0 || nx >=N || ny >=N){
                    continue;
                }

                arr[nx][ny] = 2;
                queue.offer(new int[]{nx,ny});
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 0) {
                    return false;
                }
            }
        }
        return true;
    }
}


์˜ค๋‹ต์ฒดํฌ


  • ์ž…๋ ฅ๊ณผ ๊ด€๊ณ„ ์—†์ด YES๋งŒ ์ถœ๋ ฅ๋˜๋Š” ๋ฌธ์ œ
    • map.charAt(0) - '0' -> map.charAt(j)๋กœ ๋ณ€๊ฒฝ
    • ์„ ์ƒ๋‹˜์˜ ์œ„์น˜ ์ •๋ณด๋ฅผ T๋กœ ๋ณ€๊ฒฝ
    • ํ•™์ƒ์˜ ์œ„์น˜ ์ •๋ณด๋ฅผ S๋กœ ๋ณ€๊ฒฝ
    • arr ์ž…๋ ฅ ํ˜•ํƒœ๋ฅผ String์—์„œ char๋กœ ๋ณ€๊ฒฝ
    • โญ๏ธ๊ฐ์‹œ๋ฅผ ํ”ผํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ๋ฉ”์„œ๋“œ ์ถ”๊ฐ€ํ•˜๊ธฐโญ๏ธ
...

public static boolean check() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 'T') {
                    for (int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        while (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                            if (arr[nx][ny] == 'S') return true;
                            if (arr[nx][ny] == 'O') return false;
                            nx += dx[k];
                            ny += dy[k];
                        }
                    }
                }
            }
        }
        return true;
    }


์ตœ์ข… ํ’€์ด


์‹ค์ œ ํ’€์ด ์‹œ๊ฐ„ : 1์‹œ๊ฐ„ 48๋ถ„(์‹ค์ œ ํ’€์ด ์‹œ๊ฐ„ ํฌํ•จ)

  • ์ž…๋ ฅ

    • ์ „์—ญ๋ณ€์ˆ˜ ์„ ์–ธ: N, arr, dx, dy, result
    • N ์ž…๋ ฅ๋ฐ›๊ธฐ
    • ๋ฐฐ์—ด arr ์ž…๋ ฅ๋ฐ›๊ธฐ
  • ๊ณ„์‚ฐ

    • BFS ์‹คํ–‰ํ•˜๊ธฐ
  • ์ถœ๋ ฅ

    • ๋งŒ์•ฝ ์›ํ•˜๋Š” ๊ฒฐ๊ณผ -> YES ์ถœ๋ ฅ
    • ๊ทธ๋ ‡์ง€ ์•Š๋‹ค๋ฉด -> NO ์ถœ๋ ฅ
  • ๋ณ„๋„ ๋ฉ”์„œ๋“œ

    • BFS

      • ์žฅ์• ๋ฌผ 3๊ฐœ ์„ค์น˜: ๊ฐ์‹œ๋ฅผ ํ”ผํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ๋ฉ”์„œ๋“œ๋กœ ํ™•์ธ(check)
      • N์˜ ๋ฒ”์œ„ ๋‚ด์—์„œ ๋นˆ ๊ณต๊ฐ„('X')์ธ ๊ฒฝ์šฐ ์žฅ์• ๋ฌผ ์„ค์น˜ ์ง„ํ–‰ -> count+1
      • ๋ฐฑํŠธ๋ž˜ํ‚น์œผ๋กœ ์žฅ์• ๋ฌผ ์ œ๊ฑฐ
    • check

      • ๊ฐ์‹œ๋ฅผ ํ”ผํ•  ์ˆ˜ ์žˆ๋Š”์ง€๋ฅผ ํ™•์ธํ•˜๋Š” ๋ฉ”์„œ๋“œ
      • ์„ ์ƒ๋‹˜(T) ์œ„์น˜์—์„œ ์ƒํ•˜์ขŒ์šฐ ํ™•์ธ
        • ํ•™์ƒ ๋ฐœ๊ฒฌ -> ๊ฐ์‹œ๋ฅผ ํ”ผํ•  ์ˆ˜ ์—†์Œ ์ถœ๋ ฅ(true)
        • ์žฅ์• ๋ฌผ์ด ์žˆ๋Š” ๊ฒฝ์šฐ -> false
      • ๊ฐ์‹œ๋ฅผ ๋ชจ๋‘ ํ”ผํ•œ ๊ฒฝ์šฐ -> true
import java.util.*;

public class Main {

    static int N;
    static char[][] arr;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean foundSolution;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        sc.nextLine();

        arr = new char[N][N];
        for (int i = 0; i < N; i++) {
            String map = sc.nextLine();
            for (int j = 0; j < N; j++) {
                arr[i][j] = map.charAt(j * 2); // ๊ณต๋ฐฑ
            }
        }

        foundSolution = false;
        dfs(0);

        if (foundSolution) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }

    public static void dfs(int count) {
        if (count == 3) { // ์žฅ์• ๋ฌผ 3๊ฐœ ์„ค์น˜
            if (check()) {
                foundSolution = true;
            }
            return;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 'X') {
                    arr[i][j] = 'O';
                    dfs(count + 1);
                    
                    if (foundSolution) return;
                    arr[i][j] = 'X';
                }
            }
        }
    }

    // ๊ฐ์‹œ๋ฅผ ํ”ผํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ๋ฉ”์„œ๋“œ
    public static boolean check() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 'T') {
                    for (int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        while (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                            if (arr[nx][ny] == 'S') {
                                return false; // ํ•™์ƒ ๋ฐœ๊ฒฌ ์‹œ false
                            }
                            if (arr[nx][ny] == 'O') {
                                break; // ์žฅ์• ๋ฌผ ๋ฐœ๊ฒฌ ์‹œ ์ค‘์ง€
                            }
                            nx += dx[k];
                            ny += dy[k];
                        }
                    }
                }
            }
        }
        return true; // ๋ชจ๋“  ์„ ์ƒ๋‹˜์ด ํ•™์ƒ์„ ๋ฐœ๊ฒฌํ•˜์ง€ ๋ชปํ•˜๋Š” ๊ฒฝ์šฐ์— ํ•ด๋‹น
    }
}

profile
์–ธ์  ๊ฐ€ ๋‚ด ์ฝ”๋“œ๋กœ ์„ธ์ƒ์— ๊ธฐ์—ฌํ•  ์ˆ˜ ์žˆ๋„๋ก, Data Science&BE ๊ฐœ๋ฐœ ๊ธฐ๋ก ๋…ธํŠธโ˜˜๏ธ

0๊ฐœ์˜ ๋Œ“๊ธ€

๊ด€๋ จ ์ฑ„์šฉ ์ •๋ณด

Powered by GraphCDN, the GraphQL CDN