[문제 링크]https://www.acmicpc.net/problem/1926문제 설명n × m 크기의 도화지에 있는 그림의 개수와 그림의 넓이가 가장 큰 것을 구한다.0은 색칠이 안된 부분, 1은 색칠이 된 부분이고, 1로 연결된 것을 그림 이라고 한다. 문제 풀이(1) DFS 사용import java.io.*;import java.util.StringTokenizer;public class Main { static int[][] array; static int n, m; static int area = 0, cnt = 0, maxArea = 0; static boolean[][] visited; static int[] dx = {-1, 1, 0, 0}; sta..

[문제 링크]https://www.acmicpc.net/problem/20437문제 설명알파벳 소문자로 이루어진 문자열 w와 양의 정수 k가 주어질 때, 아래 두 개에 해당되는 문자열의 길이를 구한다.- 어떤 문자를 정확히 k개 포함하는 가장 짧은 문자열의 길이- 어떤 문자를 정확히 k개 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 문자열의 길이 만족하는 문자열이 없을 경우 -1 출력 문제 풀이반복문을 사용해서 어떤 문자 k개를 포함하는 가장 짧은 문자열과 가장 긴 문자열의 길이를 구한다.처음에는 모든 경우의 수를 탐색하도록 구현했더니 시간초과가 떴다.그래서 아래와 같이 알파벳별로 개수를 세서 탐색을 실행하는 조건을 추가했다.추가한 부분1. 입력받은 문자열 w에서 각 ..

[문제 링크]https://www.acmicpc.net/problem/18428문제 설명T-선생님, S-학생, O-장애물, X-아무것도 존재하지 않음복도에 학생들이 선생님의 감시에 들키지 않도록 장애물을 설치한다.- 선생님은 본인의 위치에서 상하좌우로 감시 가능- 선생님과 학생 사이에 장애물이 있으면 학생을 볼 수 없음3개의 장애물을 설치해서 모든 학생이 선생님의 감시로부터 피할 수 있는지를 구한다. 모두 피할 수 있으면 YES, 그렇지 않으면 NO 문제 풀이복도의 정보를 입력받으면서 T(선생님)의 위치 정보를 teachers 리스트에 따로 저장한다.dfs 탐색으로 장애물 3개를 세우는 모든 경우의 수를 구한다.벽이 3개가가 된 경우, bfs 탐색으로 현재 상태에서 모든 학생이 감시를 피할 수..

[문제 링크]https://www.acmicpc.net/problem/17276문제 설명배열 X를 45도 배수만큼 시계방향 or 반시계방향으로 돌린다.시계방향으로 45도를 돌리면 아래와 같은 연산을 적용한다.1. 주대각선(왼쪽 대각선) → 가운데 열2. 가운데 열 → 부대각선(오른쪽 대각선)3. 부대각선(오른쪽 대각선) → 가운데 행5. 가운데 행 → 주대각선(왼쪽 대각선)6. 다른 원소의 위치는 변하지 않는다.반시계방향은 위 연산을 반대 방향으로 적용입력받은 회전 각도만큼 배열을 돌렸을 때, 배열을 출력한다. 문제 풀이배열을 시계방향, 반시계방향으로 돌리는 연산 규칙은 아래와 같다.시계방향으로 45도주대각선(왼쪽 대각선) → 가운데 열가운데 열 → 부대각선(오른쪽 대각선)부대각선(오른쪽 ..

[문제 링크]https://www.acmicpc.net/problem/16987문제 설명각 계란은 내구도와 무게를 가지고 있다.계란으로 계란을 치면, 각 계란의 내구도는 상대 계란의 무게만큼 깎인다.내구도가 0 이하면 계란이 깨진다.ex) 계란 1의 내구도 7 무게 5, 계란 2의 내구도 3 무게 4두 개란을 치면, 계란 1의 내구도는 7-4=3, 계란 2의 내구도는 3-5=-2 으로 계란 2가 깨진다. 일렬로 놓인 계란을 왼쪽부터 차례로 들어서 아래와 같은 규칙으로 한번씩만 쳐서 계란을 깨뜨린다.1. 가장 왼쪽 계란을 든다.2. 현재 들고있는 계란으로 깨지지 않은 다른 계란을 하나 친다. 이 때, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 넘어간다.3. 현재 들고있는 계란을 내려놓고..

[문제 링크]https://www.acmicpc.net/problem/15686문제 설명0-빈칸, 1-집, 2-치킨집 치킨거리 = 집(x1, y1)과 가장 가까운 치킨집(x2, y2) 사이의 거리 → |(x1-x2)| + |(y1-y2)|도시의 치킨거리 = 모든 집의 치킨 거리의 합 치킨집을 최대 m개를 골랐을 때, 도시의 치킨거리의 최소값을 구한다. 문제 풀이도시에 대한 정보를 입력받으면서 치킨집과 집의 위치 정보를 리스트에 따로 저장한다.dfs( ) : dfs 알고리즘을 사용해서 m개의 치킨집을 고른다. 이 때, 치킨집의 위치를 따로 저장한 리스트를 사용해서 m개의 치킨집을 고른다.houseChicken( ) : 하나의 집에 대해서 m개의 치킨집을 돌면서 거리가 가장 가까운 치킨집과의 치킨거..