적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
예를 들어, 그림이 아래와 같은 경우에
RRRBB GGBBB BBBRR BBRRR RRRRR
적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.
출력
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
예제 입력 1복사
5 RRRBB GGBBB BBBRR BBRRR RRRRR
예제 출력 1복사
4 3
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N;
static int x, y;
static ArrayList<int[]>[] graph;
static boolean[][] visit; // 이미 방문한 정점의 정보를 담을 배열
static Queue<int[]> Q;
static char[][] map;
static int[][] deltas = { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 } };
static int c = 0;
static int RG_c = 0;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
map = new char[N][N];
visit = new boolean[N][N];
for (int n = 0; n < N; n++) {
map[n] = br.readLine().toCharArray();
}
graph = new ArrayList[N * N];
for (int i = 0; i < N * N; i++) {
graph[i] = new ArrayList<int[]>();
}
// 인접 그래프 만들기 (=ok)
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < 4; k++) {
int nr = deltas[k][0] + i;
int nc = deltas[k][1] + j;
int[] n = { nr, nc };
if (nr < 0 || nc < 0 || nr >= N || nc >= N)
continue;
graph[i * N + j].add(n);
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visit[i][j]) {
int[] p = { i, j };
bfssol(p, true);
c++;
}
}
}
sb.append(c + " ");
visit = new boolean[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visit[i][j]) {
int[] p = { i, j };
bfssol(p, false);
RG_c++;
}
}
}
sb.append(RG_c);
System.out.println(sb);
}
private static void bfssol(int[] p, boolean b) {
Q = new LinkedList<int[]>();
// 시작정점을 큐에 넣어줌
Q.add(p);
// 시작정점을 방문했다는 정보 저장
visit[p[0]][p[1]] = true;
// 큐에 정점이 없어질 때까지 반복
while (!Q.isEmpty()) {
// 큐에서 정점을 poll해서 이동함
int[] q = Q.poll();
// 이동한 정점에서 연결된 정점들을 큐에 넣어주고 visit배열에 체크
for (int[] i : graph[q[0] * N + q[1]]) {
if (b) {
if (!visit[i[0]][i[1]] && map[q[0]][q[1]] == map[i[0]][i[1]]) {
Q.add(i);
visit[i[0]][i[1]] = true;
}
} else {
if (!visit[i[0]][i[1]] && ((map[q[0]][q[1]] == 'R' && map[i[0]][i[1]] == 'G')
|| (map[q[0]][q[1]] == 'G' && map[i[0]][i[1]] == 'R')
|| map[q[0]][q[1]] == map[i[0]][i[1]])) {
Q.add(i);
visit[i[0]][i[1]] = true;
}
}
}
}
}
}
N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.
지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
지붕의 가장자리는 땅에 닿아야 한다.
비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.
그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.
그림1 . 기둥과 지붕(굵은 선)의 예
창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.
기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.
입력
첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.
출력
첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BJ_02304 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int TC = Integer.parseInt(br.readLine());
int result = 0;
int[][] polls = new int[TC][2];
int tallest = Integer.MIN_VALUE;
for (int t = 0; t < TC; t++) {
st = new StringTokenizer(br.readLine(), " ");
polls[t][0] = Integer.parseInt(st.nextToken());
polls[t][1] = Integer.parseInt(st.nextToken());
}
// 기둥을 x 좌표 순서로 정렬
Arrays.sort(polls, (s1, s2) -> Integer.compare(s1[0], s2[0]));
// 기둥의 시작부터 끝까지 탐색하며 높은 기둥이 나올 때마다 높은 기둥수로 tallest 갱신해 result에 +=tallest
for (int i = polls[0][0], k = 0; i <= polls[TC - 1][0]; i++) {
if (polls[k][0] == i) {
if (tallest < polls[k][1]) {
tallest = polls[k][1];
}
k++;
}
result += tallest;
}
if (TC <= 1) {
System.out.println(result);
return;
}
// 뒷부분 처리
//가장 높은 기둥과, 뒤에서부터 탐색한 가장 높은 기둥과의 차이를 빼주기
//차이-> tallest-backtallest
int backtallest = Integer.MIN_VALUE;
int difference = 0;
for (int i = polls[TC - 1][0], k = TC -1 ; i >= polls[0][0]; i--) {
//i갸 기둥을 만났을 때
if (polls[k][0] == i) {
//앞에서부터 체크한 가장 높은 기둥 tallest와 만나면 break
if(tallest == polls[k][1] && polls[k][0] == i) break;
//뒤에서부터 체크한 tallest보다 현재 만난 기둥이 더 높으면 backtallest와 difference 갱신
if (backtallest < polls[k][1]) {
backtallest = polls[k][1];
difference = tallest-backtallest ;
}
//다음 기둥
k--;
}
//차이 빼주기
result -= difference;
}
System.out.println(result);
}
}
높은 기둥이 갱신될 때마다 tallest 변수를 갱신해 poll[0]의 x좌표부터 poll[TC-1] x좌표까지 방문하며 누적 합하고
(line 23~32)
가장 높은 기둥이 tallest를 만날 때까지 뒤에서부터 차이를 갱신하며 누적합에서 차이를 빼주는 방식으로 풀이하였습니다.
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 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를 출력하면 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int V, E;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
st = new StringTokenizer(br.readLine(), " ");
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(br.readLine());
int start = K;
final int INFINITY = Integer.MAX_VALUE;
ArrayList<ArrayList<int[]>> adList = new ArrayList<ArrayList<int[]>>();
for (int i = 0; i <= V; i++)
adList.add(new ArrayList<int[]>());
int[] distance = new int[V + 1];
boolean[] visited = new boolean[V + 1];
for (int i = 0; i < E; ++i) {
st = new StringTokenizer(br.readLine(), " ");
int u = Integer.parseInt(st.nextToken());
int[] dwset = new int[2];
dwset[0] = Integer.parseInt(st.nextToken());
dwset[1]= Integer.parseInt(st.nextToken());
adList.get(u).add(dwset);
}
Arrays.fill(distance, INFINITY);
distance[start] = 0;
int min = 0, current = 0;
for (int i = 0; i < V; ++i) {
// a단계 : 방문하지 않은 정점들 중 최소가중치의 정점 선택
min = INFINITY;
for (int j = 1; j <= V; ++j) {
if (!visited[j] && distance[j] < min) {
min = distance[j];
current = j;
}
}
visited[current] = true; // 선택 정점 방문 처리
// b단계: current정점을 경유지로 하여 갈수 있는 다른 방문하지 않은 정점들에 대한 처리
for (int[] c: adList.get(current)) {
if (!visited[c[0]] && distance[c[0]] > min + c[1]) {
distance[c[0]] = min + c[1];
}
}
}
//출력부
for (int j = 1; j <= V; j++) {
if (distance[j] == INFINITY) {
sb.append("INF\n");
continue;
}
sb.append(distance[j] + "\n");
}
System.out.println(sb);
}
}
인접리스트에 인접한 정점과 가중치를 담은 int형 배열을 담아 방문하지 않은 정점 중 최소 가중치의 정점을 선택해
어떤 공연장에는 가로로 C개, 세로로 R개의 좌석이 C×R격자형으로 배치되어 있다. 각 좌석의 번호는 해당 격자의 좌표 (x,y)로 표시된다.
예를 들어보자. 아래 그림은 가로 7개, 세로 6개 좌석으로 구성된 7×6격자형 좌석배치를 보여주고 있다. 그림에서 각 단위 사각형은 개별 좌석을 나타내며, 그 안에 표시된 값 (x,y)는 해당 좌석의 번호를 나타낸다. 가장 왼쪽 아래의 좌석번호는 (1,1)이며, 가장 오른쪽 위 좌석의 번호는 (7,6)이다.
(1, 6)
(7, 6)
(4, 4)
(7, 4)
(1, 3)
(6, 3)
(1, 2)
(1, 1)
(2, 1)
(3, 1)
(7, 1)
이 공연장에 입장하기 위하여 많은 사람이 대기줄에 서있다. 기다리고 있는 사람들은 제일 앞에서부터 1, 2, 3, 4, . 순으로 대기번호표를 받았다. 우리는 대기번호를 가진 사람들에 대하여 (1,1)위치 좌석부터 시작하여 시계방향으로 돌아가면서 비어있는 좌석에 관객을 순서대로 배정한다. 이것을 좀 더 구체적으로 설명하면 다음과 같다.
먼저 첫 번째 사람, 즉 대기번호 1인 사람은 자리 (1,1)에 배정한다. 그 다음에는 위쪽 방향의 좌석으로 올라가면서 다음 사람들을 배정한다. 만일 더 이상 위쪽 방향으로 빈 좌석이 없으면 오른쪽으로 가면서 배정한다. 오른쪽에 더 이상 빈자리가 없으면 아래쪽으로 내려간다. 그리고 아래쪽에 더 이상 자리가 없으면 왼쪽으로 가면서 남은 빈 좌석을 배정한다. 이 후 왼쪽으로 더 이상의 빈 좌석이 없으면 다시 위쪽으로 배정하고, 이 과정을 모든 좌석이 배정될 때까지 반복한다.
아래 그림은 7×6공연장에서 대기번호 1번부터 42번까지의 관객이 좌석에 배정된 결과를 보여주고 있다.
6
7
8
9
10
11
12
5
26
27
28
29
30
13
4
25
38
39
40
31
14
3
24
37
42
41
32
15
2
23
36
35
34
33
16
1
22
21
20
19
18
17
여러분은 공연장의 크기를 나타내는 자연수 C와 R이 주어져 있을 때, 대기 순서가 K인 관객에게 배정될 좌석 번호 (x,y)를 찾는 프로그램을 작성해야 한다.
입력
첫 줄에는 공연장의 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 1,000이다. 그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다. 단 1 ≤ K ≤ 100,000,000이다.
출력
입력으로 제시된 대기번호 K인 관객에게 배정될 좌석번호 (x,y)를 구해서 두 값, x와 y를 하나의 공백을 사이에 두고 출력해야 한다. 만일 모든 좌석이 배정되어 해당 대기번호의 관객에게 좌석을 배정할 수 없는 경우에는 0(숫자 영)을 출력해야 한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BJ_10157 {
static int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int C = Integer.parseInt(st.nextToken());
int R = Integer.parseInt(st.nextToken());
int p = Integer.parseInt(br.readLine());
if (R * C < p) {
System.out.println(0);
return;
}
int num = 0;
int[][] arr = new int[R + 1][C + 1];
for (int k = 0; k <= Integer.max(R, C); k++) {
int t = 2 * k + 1;
int borderlength = (R - t) * 2 + (C - t) * 2;
if (borderlength == 0) {
System.out.println(1+" " + 1);
return;
}
if (p > num + borderlength) {
num += borderlength;
continue;
}
int x = k;
int y = k + 1;
int i = 0;
int temp = 0;
while (p != num) {
num++;
temp++;
x += dir[i][0];
y += dir[i][1];
arr[x][y] = num;
if (temp == R - 2 * k)
i = 1;
if (temp == R - 2 * k + C - 2 * k - 1)
i = 2;
if (temp == R - 2 * k + C - 2 * k - 1 + R - 2 * k - 1)
i = 3;
}
System.out.println(y + " " + x);
return;
}
}
}
둘레의 길이보다 크면 더 안쪽의 둘레로 들어가 수행 시간을 단축할 수 있도록 가장 바깥쪽 둘레부터 한칸씩 안쪽으로 검사해 주었습니다.
//둘레의 길이 borderlength
int borderlength = (R - t) * 2 + (C - t) * 2;
//예외 처리(1,1)인 경우(둘레의 길이가 0) if (borderlength == 0) { System.out.println(1+" " + 1); return; }
//검사(조건이 true면 안쪽으로 들어가기) if (p > num + borderlength) { num += borderlength; continue; }
더이상 안쪽으로 들어가지 않아도 된다면 이전 둘레의 마지막 좌표에서 시작하여
int x = k; int y = k + 1;
temp가 경계에 닿으면 방향을 전환하도록 작성해주었습니다.
if (temp == R - 2 * k) i = 1; if (temp == R - 2 * k + C - 2 * k - 1) i = 2; if (temp == R - 2 * k + C - 2 * k - 1 + R - 2 * k - 1) i = 3;
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
입력
첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.
출력
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class BJ_01987 {
static int R, C;
static char[][] map;
static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
static int result, cnt;
static List<Character> stamp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new char[R][C];
for (int i = 0; i < R; i++) {
map[i] = br.readLine().toCharArray();
}
//stamp 초기화
stamp = new ArrayList<Character>();
//말이 밟고 있는 제일 첫칸도 포함하므로
//stamp에 map[0][0]을 넣어주고 시작
//cnt, result=1로 초기화
stamp.add(map[0][0]);
cnt = 1;
result =1;
horse(0, 0);
//출력
System.out.println(result);
}
static void horse(int r, int c) {
//상하좌우 탐색
for (int i = 0; i < 4; i++) {
int dr = r + delta[i][0];
int dc = c + delta[i][1];
//인덱스 넘어가면 수행 x
if (dr < 0 || dr == R || dc < 0 || dc == C)
continue;
//갈 수 있는지 검사
if (isAvailable(dr, dc)) {
//갈수 있다면 cnt++ 하고 최댓값 갱신
cnt++;
if(result < cnt) result = cnt;
//stamp에 지나온 알파벳 추가
stamp.add(map[dr][dc]);
//이동
horse(dr, dc);
//되돌아오므로 stamp와 cnt도 되돌려줌
stamp.remove(stamp.size()-1);
cnt--;
}
}
}
static boolean isAvailable(int r, int c) {
//접근할 좌표의 알파벳이 지금껏 지나온 알파벳 중 같은 것이 있다면
for (char ch : stamp) {
if (map[r][c] == ch)
//접근 불가
return false;
}
//아무것도 겹치지 않는다면 접근 가능
return true;
}
}
