먹여살릴냥꽁이가있습니다.

문제

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

출력

첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

예제

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class Main_BJ_1062_가르침 {     static int result,N,K;     static boolean [] alphbet;     static String [] words;       public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st ;                  st = new StringTokenizer(br.readLine()," ");                  N = Integer.parseInt(st.nextToken());         K = Integer.parseInt(st.nextToken());                  if(K<5) {             System.out.println(0);             return;         }else if(K==26) {             System.out.println(N);             return;         }                  alphbet = new boolean[26];         alphbet['a'-'a']=true;         alphbet['n'-'a']=true;         alphbet['t'-'a']=true;         alphbet['i'-'a']=true;         alphbet['c'-'a']=true;              words = new String[N];         for(int i=0;i<N;i++) {             String str = br.readLine().replaceAll("anta|tica", "");             words[i] = str;         }                      check(0,0);         System.out.println(result);     }          static void check(int index, int cnt) {         if(cnt==K-5) {             wordCheck();             return;         }                  for(int i=index; i<26;i++) {             if(!alphbet[i]) {                 alphbet[i]= true;                 check(i, cnt+1);                 alphbet[i]=false;             }         }     }          static void wordCheck() {         int count=0;                  for(int i=0;i<N;i++) {             boolean check=true;                          for(int j=0;j<words[i].length();j++) {                 if(!alphbet[words[i].charAt(j)-'a']) {                     check= false;                     break;                 }             }             if(check) count++;         }         result = Math.max(result, count);     }      } Colored by Color Scripter

cs

 

문제

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

입력

첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.

출력

첫째 줄에 가장 짧은 다리의 길이를 출력한다.

예제

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class Main_BJ_2146_다리만들기 {     static int N, min =Integer.MAX_VALUE;     static int [][] map;     static boolean [][] visited;     static int [] dx = {-1,0,1,0};     static int [] dy = {0,1,0,-1};       public static void main(String[] args) throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;                  N = Integer.parseInt(br.readLine());                  map = new int[N][N];         visited = new boolean[N][N];                  for(int i=0;i<N;i++) {             st = new StringTokenizer(br.readLine()," ");             for(int j=0;j<N;j++) {                 map[i][j] =Integer.parseInt(st.nextToken());             }         }                  int count=1;         for(int i=0;i<N;i++) {             for(int j=0;j<N;j++) {                 if(map[i][j]==1 && !visited[i][j]) {                     count++;                      counting(i,j,count);                 }                 }         }                  for(int i=0;i<N;i++) {             for(int j=0;j<N;j++) {                 if(map[i][j]!=0) {                     visited = new boolean[N][N];                     bridge(i,j);                 }             }         }         System.out.println(min);     }          public static void bridge(int x, int y) {         int num = map[x][y];         Queue<int []> queue = new LinkedList<int[]>();         visited[x][y] = true;         queue.offer(new int[] {x,y,0});                  while(!queue.isEmpty()) {             int[] info = queue.poll();                          for(int i=0;i<4;i++) {                 int nx = info[0]+dx[i];                 int ny = info[1]+dy[i];                                  if(range(nx,ny) && !visited[nx][ny]) {                     visited[nx][ny] = true;                     if(map[nx][ny]==0) {                         queue.offer(new int[] {nx,ny, info[2]+1});                     }                     else if(map[nx][ny]!=num) {                         min = Math.min(info[2], min);                         return;                     }                                      }                              }         }     }               public static void counting(int x, int y, int count) {         Queue<int []> queue = new LinkedList<int[]>();         map[x][y] = count;         visited[x][y] = true;         queue.offer(new int[] {x,y});                  while(!queue.isEmpty()) {             int[] info = queue.poll();                          for(int i=0;i<4;i++) {                 int nx = info[0]+dx[i];                 int ny = info[1]+dy[i];                                  if(range(nx,ny) && map[nx][ny]==1 && !visited[nx][ny]) {                     map[nx][ny]=count;                      visited[nx][ny] = true;                     queue.offer(new int[] {nx,ny});                 }             }         }     }          public static boolean range(int x, int y) {         return x>=0 && y>=0 && x<N && y<N;     }   } Colored by Color Scripter

cs

 

풀이 방법

지도가 주어질 때, 가장 짧은 다리를 하나 놓아 두 대륙을 연결할 수 있는 다리의 최소 길이를 구하는 문제였습니다. 먼저 count 변수를 통해 각 대륙들을 구분해 주었습니다. 그리고 한 대륙에서 다른 대륙으로 다리를 놓을 수 있는지 확인하기 위해 bfs() 메소드를 통해 상하좌우로 이동하면서 다른 대륙으로 연결할 수 있는지 확인해주었습니다. 만약 도착한 대륙이 출발한 대륙의 번호와 일치하지 않은 경우에는 두 대륙을 연결할 수 있는 다리를 놓을 수 있으므로 min 변수에 다리 길이를 넣어 리턴해주었습니다. 다리를 연결할 수 있는 모든 경우를 확인해 다리의 최소 길이를 구해주었습니다.

문제

고대 미스테리로 전해지는 여우의 울음소리를 밝혀내기 위해 한신이는 고성능 녹음기로 무장하고 숲으로 들어갔다. 하지만 숲에는 동물들이 가득해, 녹음된 음성에는 다른 동물들의 울음소리가 섞여 있다. 그러나 한신이는 철저한 준비를 해 왔기 때문에 다른 동물들이 어떤 울음소리를 내는지 정확히 알고 있다. 그러므로 그 소리를 모두 걸러내면 남은 잡음은 분명히 여우의 울음소리일 것이다.

입력

첫 번째 줄에는 테스트케이스의 개수 T가 입력된다. 각 테스트케이스는 아래와 같이 구성되어 있다.

테스트케이스의 첫 줄에는 몇 개의 단어로 이루어진 녹음된 소리가 입력된다. 단어는 알파벳 소문자로만 이루어져 있으며 공백으로 구분된다. 단어의 길이는 최대 100글자이고, 단어의 개수는 최대 100개이다. 다음 줄부터는 여우를 제외한 동물들의 울음소리가 <동물> goes <소리>의 형태로 입력된다. 최소 1마리, 최대 100마리이며, 이름은 최대 100글자이고 실제로 존재하는 동물의 이름이다. 여우를 제외한 동물의 울음소리는 한 단어이고 최대 100글자이다.

마지막 줄에는 한신이가 알고 싶어하는 질문이 주어진다. what does the fox say?

출력

각 테스트케이스마다 여우의 울음소리를 한 줄씩, 녹음된 순서대로 출력한다. 여우의 울음소리가 녹음되어 있음이 보장된다. (알려진 것과는 달리, 여우는 모스 부호로 의사소통하지 않는다.)

예제

코드

풀이 방법

여우의 울음소리를 한 줄씩, 녹음된 순서대로 출력하는 문제였습니다. 여우를 제외한 동물들의 울음소리가 <동물> goes <소리>의 형태로 입력되기 때문에 띄어쓰기를 기준으로 단어를 나누었을 때, 세 번째 단어가 the가 아닐 경우에는 list에 넣어둔 울음소리 중 동일한 동물의 소리를 list에서 제거해주었습니다. 만약 세 번째 단어가 the일 경우에는 while문을 빠져나와 남은 울음소리를 차례대로 출력해주었습니다.

문제

용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다.

마왕은 용사를 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈 하고 싶은 용사는 반드시 T시간 내에 공주님이 있는 곳에 도달해야 한다. 용사는 한 칸을 이동하는 데 한 시간이 걸린다. 공주님이 있는 곳에 정확히 T시간만에 도달한 경우에도 구출할 수 있다. 용사는 상하좌우로 이동할 수 있다.

성에는 이전 용사가 사용하던 전설의 명검 "그람"이 숨겨져 있다. 용사가 그람을 구하면 마법의 벽이 있는 칸일지라도, 단숨에 벽을 부수고 그 공간으로 갈 수 있다. "그람"은 성의 어딘가에 반드시 한 개 존재하고, 용사는 그람이 있는 곳에 도착하면 바로 사용할 수 있다. 그람이 부술 수 있는 벽의 개수는 제한이 없다.

우리 모두 용사가 공주님을 안전하게 구출 할 수 있는지, 있다면 얼마나 빨리 구할 수 있는지 알아보자.

입력

첫 번째 줄에는 성의 크기인 N, M 그리고 공주에게 걸린 저주의 제한 시간인 정수 T가 주어진다. 첫 줄의 세 개의 수는 띄어쓰기로 구분된다. (3 ≤ N, M ≤ 100, 1 ≤ T ≤ 10000)

두 번째 줄부터 N+1번째 줄까지 성의 구조를 나타내는 M개의 수가 띄어쓰기로 구분되어 주어진다. 0은 빈 공간, 1은 마법의 벽, 2는 그람이 놓여있는 공간을 의미한다. (1,1)과 (N,M)은 0이다.

출력

용사가 제한 시간 T시간 이내에 공주에게 도달할 수 있다면, 공주에게 도달할 수 있는 최단 시간을 출력한다.

만약 용사가 공주를 T시간 이내에 구출할 수 없다면, "Fail"을 출력한다.

예제

코드

풀이 방법

용사가 제한 시간 T시간 이내에 공주에게 도달할 수 있는 최단 시간을 구하는 문제였습니다. 예전에 이 문제와 비슷한 문제를 접해본 적이 있어 3차원 배열을 이용해 빠르게 방향을 잡을 수 있었습니다. 먼저 용사의 위치인 (0,0)을 시간과 함께 큐에 넣어주었습니다. 용사가 상하좌우로 움직이면서 전설의 명검인 그람을 구하면 벽이 있는 칸일지라도, 벽을 부수고 이동할 수 있기 때문에 3차원 배열을 이용해 그람을 가지고 있을 때와 가지고 있지 않을 때를 나눠주었습니다. 만약 그람을 가지고 있을 경우에는 방문하지 않은 곳이라면 어디든지 이동할 수 있으므로 바로 방문처리와 함께 큐에 넣어주고, 그람을 가지고 있지 않은 경우에는 벽이 아닌 길인 곳으로만 이동할 수 있으므로 다음 이동할 곳이 그람인지 길인지를 확인해 큐에 넣어주었습니다. 이 과정을 반복해 만약 용사가 제한시간 T시간 내에 공주님이 있는 (N-1, M-1)에 도착했다면 최단 시간을 출력해주고 아닌 경우에는 Fail를 출력해주었습니다.

문제

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 

출력

각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

예제

코드

풀이 방법

두 변을 공유하지 않는 스티커 점수의 최댓값을 구하는 문제였습니다. 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없기 때문에, 스티커 점수의 합을 저장해 줄 dp [][] 배열에 현재 뗄 스티커를 기준으로 다른 줄에 있는 스티커 중 해당 스티커의 왼쪽에 있는 2개의 스티커의 점수를 비교해 더 큰 값을 해당 스티커의 값과 더해줬습니다. 마지막으로 첫 번째 줄의 맨 오른쪽에 있는 값과 두 번째 줄의 맨 오른쪽에 있는 값을 비교해 더 큰 값을 출력해주었습니다.

문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

예제

코드

풀이 방법

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하는 문제였습니다. 준규는 위치한 곳에서 오른쪽, 아래, 오른쪽 아래 대각선으로 이동할 수 있으므로, 해당 위치에서 위쪽, 왼쪽, 왼쪽 위 대각선 중에서 가장 큰 값과 해당 위치의 값을 더해주면서 (N, M)에 도착했을 때의 값을 출력해주었습니다.

문제

코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.

이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다. 

통로에 떨어진 음식물을 피해 가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다. 

선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.

입력

첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다.  그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.

좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다.

출력

첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.

예제

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class Main_BJ_1743_ {          static class info{         int x, y;           public info(int x, int y) {             this.x = x;             this.y = y;         }     }          static int N,M,K, ans;     static int [][] map;     static boolean [][] visited;     static int [] dx = {-1,0,1,0};     static int [] dy = {0,1,0,-1};       public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;                  st = new StringTokenizer(br.readLine()," ");                  N = Integer.parseInt(st.nextToken());         M = Integer.parseInt(st.nextToken());         K = Integer.parseInt(st.nextToken());                  map = new int[N][M];         visited = new boolean[N][M];                  for(int i=0;i<K;i++) {             st = new StringTokenizer(br.readLine()," ");             map[Integer.parseInt(st.nextToken())-1][Integer.parseInt(st.nextToken())-1]=1;         }                  for(int i=0;i<N;i++) {             for(int j=0;j<M;j++) {                 if(map[i][j]==1 && !visited[i][j]) bfs(i,j);             }         }         System.out.println(ans);       }          public static void bfs(int x, int y) {         Queue<info> queue = new LinkedList<>();         queue.offer(new info(x,y));         visited[x][y]=true;                  int count=1;         while(!queue.isEmpty()) {             info temp = queue.poll();                          for(int i=0;i<4;i++) {                 int nx = temp.x+dx[i];                 int ny = temp.y+dy[i];                                  if(range(nx,ny) && !visited[nx][ny] && map[nx][ny]==1) {                     visited[nx][ny]=true;                     queue.offer(new info(nx,ny));                     count++;                 }             }             ans = Math.max(ans, count);         }              }     public static boolean range(int x, int y) {         return x>=0 && y>=0 && x<N && y<M;     } } Colored by Color Scripter

cs

 

풀이 방법

음식물 중 가장 큰 음식물의 크기를 구하는 문제였습니다. 먼저 음식물이 떨어진 좌표를 map배열 해당 위치에 1의 값을 넣어줘 음식물이 떨어진 곳과 아닌 곳을 구분해주었습니다. 그리고 이중 for문을 이용해 해당 map 좌표에 음식물이 있고 방문하지 않았던 곳이라면 bfs()를 통해 상 하 좌 우를 탐색해 음식물의 크기를 구했습니다. 탐색이 끝난 후, 가장 큰 음식물의 크기를 구하는 문제이기 때문에 기존 값과 현재 구한 크기를 비교해 더 큰 값을 출력해주었습니다.

문제

N×M (5≤N, M≤100)의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한 시간 만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부 공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

출력

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

예제

코드

풀이방법

치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 문제였습니다. 이 문제에서 체크해야 할 부분이 치즈 격자의 4변 중에서 적어도 2변 이상이 공기와 접촉했을 경우 한시간 뒤 치즈가 녹는다는 점과, 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는다는 점입니다. 치즈가 상 하 좌 우 중 접촉하고 있는 변의 수를 세기 위해 cheese 배열을 만들어 탐색할 곳이 치즈라면 그 곳의 수를 늘려주는 방식으로 구현했습니다. 탐색을 끝낸 후, 2변 이상 공기와 접촉한 치즈는 녹아 없어지므로 0으로 바꿔주고 치즈가 몇 개 남아있는지 확인해 주었습니다. 격자에 치즈가 하나도 존재하지 않을 경우 while문을 종료하고 걸린 시간을 출력해주었습니다.

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

예제

코드

풀이방법

 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 하는데 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 즉 벽을 세워 얻을 수 있는 안전 영역의 최대 크기를 구하는 문제였습니다. 무조건 벽을 3개를 세워야 하기 때문에 해당 위치가 빈칸일 경우에는 벽을 세워 3개의 벽을 다 세웠을 경우에 bfs() 메서드를 통해 바이러스를 퍼지게 하고 safeZone() 함수를 통해 바이러스가 더 퍼지고 난 후, 안전 영역의 칸 수를 확인해 주었습니다. 벽을 세우는 위치에 따라 안전영역수를 카운트해줌으로써 가장 최대의 안전 영역을 구해주었습니다.

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

예제

코드

풀이 방법

(1,1)에서 (N, M)의 위치까지 이동하는데 걸리는 최단 경로를 구하는 문제였습니다. 만약 한 개의 벽을 부수고 이동하는 것이 좀 더 짧은 경로라면, 벽을 한 개까지 부수고 이동해도 되는 것이 중요한 부분이었습니다.

저는 벽을 부수고 이동했는지 아닌지를 확인해주기 위해 3차원 배열을 이용하여 구현해보았습니다. 첫 출발지 정보를 우선순위 큐에 넣어놓고 BFS 알고리즘을 이용했습니다. 만약 벽을 부수고 이동한 적이 없지만 이동할 곳이 벽이라면 부실수 있으므로 visited [][][1]에 부수고 이동했다는 의미인 true와 큐에 해당 위치 정보들을 넣어주었습니다. 반대로 벽이 아닌 이동할 수 있는 곳이고 방문하지 않은 곳이라면 방문했다는 표시와 함께 큐에 위치 정보들을 넣어주었습니다. 반복적으로 while 문을 돌면서 해당 위치가 목적지인 (N, M)에 도착했다면 이동 횟수를 출력해주었습니다.