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

문제

코레스코 콘도미니엄 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)에 도착했다면 이동 횟수를 출력해주었습니다.

최소신장트리(MST)란?

• 무향 가중치 그래프에서 신장트리를 구성하는 간선들의 가중치 합이 최소인 신장트리
  • Kruskal 알고리즘
  • Prim 알고리즘

Kruskal

• 간선을 하나씩 선택해서 MST를 찾는 알고리즘
  1. 모든 간선을 가중치에 따라 오름차순 정렬
  2. 가중치가 낮은 순서대로 간선을 선택하며 사이클이 발생하지 않도록 간선 선택
  3. N-1개의 간선이 선택될 때까지 2번 반복 수행

• 코드

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

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer;   public class Kruskal {     static class Edge implements Comparable<Edge>{         int start, end, weight;           public Edge(int start, int end, int weight) {             this.start = start;             this.end = end;             this.weight = weight;         }           @Override         public int compareTo(Edge o) {             return this.weight-o.weight;         }     }          static int V,E,A,B,C;     static int [] parents;     static Edge[] edgeList;       public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;                  st = new StringTokenizer(br.readLine()," ");                  V = Integer.parseInt(st.nextToken());         E = Integer.parseInt(st.nextToken());                  parents = new int[V+1];         edgeList = new Edge[E];                  for(int i=0;i<E;i++) {             st = new StringTokenizer(br.readLine()," ");             A = Integer.parseInt(st.nextToken());             B = Integer.parseInt(st.nextToken());             C = Integer.parseInt(st.nextToken());                          edgeList[i] = new Edge(A,B,C);         }                  make();                  Arrays.sort(edgeList);         int result = 0, count=0;         for(Edge edge : edgeList){             if(union(edge.start,edge.end)){ // 싸이클이 발생하지 않았으면                 result += edge.weight;                 count++;                                 if(count == V-1){ // 연결 간선수가 정점수-1이면 다 연결                     break;                 }                         }         }         System.out.println(result);       }          public static void make() {         for(int i=0;i<V;i++) parents[i]= i;     }          public static boolean union(int a, int b) {         int aRoot = find(a);         int bRoot = find(b);                  if(aRoot != bRoot) {             parents[bRoot] = aRoot;             return true;         }         return false;     }          public static int find(int x) {         if(parents[x]==x) return x;         return parents[x]= find(parents[x]);     }   } Colored by Color Scripter

cs

 

Prim

• 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어가는 방식
  1. 임의 정점을 하나 선택
  2. 선택한 정점과 인접하는 정점들 중에 최소 비용 간선이 존재하는 장점 선택
  3. 모든 정점이 선택될 때 까지 1, 2번 반복

---

• 코드

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

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer;   public class Prim{     public static void main(String[] args) throws Exception {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         int N = Integer.parseInt(br.readLine().trim());         int[][] input = new int[N][N];         boolean[] visited = new boolean[N];         int[] minEdge = new int[N];                  StringTokenizer st;         for (int i = 0; i < N; i++) {             st = new StringTokenizer(br.readLine());             for (int j = 0; j < N; j++) {                 input[i][j] = Integer.parseInt(st.nextToken());             }             minEdge[i] = Integer.MAX_VALUE;         }// i노드에서 j노드까지의 비용을 모두 배열에 저장                  int minVertex,min,result = 0;         minEdge[0] = 0; // 임의의 시작점 비용 0 셋팅                  for(int c = 0 ; c< N; c++){// 모든 정점 수만큼 반복             min = Integer.MAX_VALUE;// 초기값으로 정수의 최대치를 주고 시작             minVertex = 0;                          for(int i=0; i<N; ++i) {                  if(!visited[i] &&  min > minEdge[i] ) {                     min = minEdge[i];                     minVertex = i;                 }             }                              result += min;              visited[minVertex] = true;                           for (int i = 0; i < N; i++) {                  if (!visited[i] && input[minVertex][i] != 0 &&  minEdge[i] > input[minVertex][i]  ) {                     minEdge[i] = input[minVertex][i];                 }             }         }         System.out.println(result);     } } Colored by Color Scripter

cs

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

예제

코드

문제

상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다.

상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다.

링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 링의 개수 N이 주어진다. (3 ≤ N ≤ 100)

다음 줄에는 링의 반지름이 상근이가 바닥에 놓은 순서대로 주어진다. 반지름은 1과 1000를 포함하는 사이의 자연수이다.

출력

출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다.

예제

코드

풀이방법

첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 문제였습니다. 저는 첫 번째 링과 해당 링의 최대 공배수를 구해 각각 최대 공약수로 나눠주는 방법으로 구현했습니다.

문제

n×n 바둑판 모양으로 총 n2개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작 방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.

시작 방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작 방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.

아래 그림은 n=8인 경우의 한 예이다.

위 그림에서는 두 개의 검은 방(예를 들어 (4,4)의 방과 (7,8)의 방)을 흰 방으로 바꾸면, 시작 방에서 끝방으로 갈 수 있지만, 어느 검은 방 하나만을 흰 방으로 바꾸어서는 불가능하다. 검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성하시오.

단, 검은 방을 하나도 흰방으로 바꾸지 않아도 되는 경우는 0이 답이다.

입력

첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.

출력

첫 줄에 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 출력한다.

예제

코드

풀이방법

(1,1)에서 (N, N)으로 가야 하는데 검은 방은 들어갈 수 없으므로 흰 방으로만 들어갈 수 있다. 만약 시작 방에서 끝 방으로 갈 수 없을 경우에는 검은 방을 흰방으로 바꿀 수 있다. 시작방에서 끝 방으로 갈 때 흰 방으로 바꾸어야 할 최소의 검은 방 수를 구하는 문제였습니다. 시작 위치인 (0,0)를 우선순위 큐에 넣어두고 상하좌우 탐색을 시작해 이동했습니다. 만약 이동하다가 해당 위치가 검은 방일 경우에는 벽을 부수고 이동하고 흰 방인 경우에는 그냥 이동하는 정보를 우선순위 큐에 넣어주었습니다. 우선순위 큐에는 벽을 부슨 횟수를 정렬하고 있으므로 큐의 맨 앞에 값이 가장 적은 수의 검은 방을 부수면서 도착지점까지 간 정보를 담고 있으므로 만약 해당 위치 값이 도착지일 때의 벽을 부순 횟수를 리턴해주었습니다.