Dailelog
b10026.java 백준 적록색약 본문
적록색약 성공다국어
시간 제한메모리 제한제출정답맞힌 사람정답 비율
| 1 초 | 128 MB | 49598 | 28536 | 21851 | 56.518% |
문제
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
예를 들어, 그림이 아래와 같은 경우에
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.
출력
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
이 문제를 다른 BFS처럼 동일한 방식으로 풀수 있다. 전에 풀었던 그림(https://basakreview.tistory.com/43) 문제에서 적록색약이라는 조건을 하나를 생각해주면 풀리게 되는데 처음에는 인텔리제이에서는 원한는데로 출력값이 잘나와서 아래의 코드를 백준에 제출하였지만 동일하게 4%에서 틀리는 현상이 발생하여 코드를 수정해 제출했다. 아래의 코드가 이중for문의 사용을 줄인 코드여서 코드 적으로 깔끔한것 같지만 백준사이트에서 반례가 존재하는 듯하다.
import java.io.*;
import java.util.*;
public class b10026 {
public static class Pos {
int pos_x;
int pos_y;
Pos(int x, int y) {
pos_x = x;
pos_y = y;
}
}
public static void main(String[] args) throws Exception {
int N;
int x;
int y;
int numOfpaintR = 0;
int numOfpaintG = 0;
int numOfpaintB = 0;
int numOfpaintRG = 0;
String stringBuffer;
int[][] paint;
boolean[][] isUsed;
boolean[][] isUsedGR;
char[] charBuffer ;
Queue<Pos> queueR = new LinkedList<>();
Queue<Pos> queueG = new LinkedList<>();
Queue<Pos> queueB = new LinkedList<>();
Queue<Pos> queueRG = new LinkedList<>();
Pos tmpPos;
Pos posBuffer;
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
paint = new int[N][N];
isUsed = new boolean[N][N];
isUsedGR = new boolean[N][N];
charBuffer = new char[N];
for (int i = 0; i < N; i++) {
stringBuffer = br.readLine();
for (int j = 0; j < N; j++) {
charBuffer[j] = stringBuffer.charAt(j);
if (charBuffer[j]== 'R') {
paint[i][j] = 1;
} else if (charBuffer[j] == 'G') {
paint[i][j] = 2;
} else if (charBuffer[j] == 'B') {
paint[i][j] = 3;
}
}
}
/*
//주어지는 입력이 String 한줄인데 착각으로 nextToken을 받으면 각으로 끝는걸 까먹음
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
if (st.nextToken() == "R") {
paint[i][j] = 1;
} else if (st.nextToken() == "G") {
paint[i][j] = 2;
} else if (st.nextToken() == "B") {
paint[i][j] = 3;
}
}
}
*/
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (paint[i][j] == 1 && !isUsed[i][j]) {
posBuffer = new Pos(i,j);
queueR.add(posBuffer);
numOfpaintR++;
while(!queueR.isEmpty()) {
tmpPos = queueR.poll();
for (int k = 0; k < dx.length; k++) {
x = tmpPos.pos_x + dx[k];
y = tmpPos.pos_y + dy[k];
if (-1 < x && x < N && -1 < y && y < N) {
if (paint[x][y] == 1 && !isUsed[x][y]){
posBuffer = new Pos(x,y);
queueR.add(posBuffer);
isUsed[x][y] = true;
}
}
}
}
}
else if (paint[i][j] == 2 && !isUsed[i][j]) {
posBuffer = new Pos(i,j);
queueG.add(posBuffer);
numOfpaintG++;
while(!queueG.isEmpty()) {
tmpPos = queueG.poll();
for (int k = 0; k < dx.length; k++) {
x = tmpPos.pos_x + dx[k];
y = tmpPos.pos_y + dy[k];
if (-1 < x && x < N && -1 < y && y < N) {
if (paint[x][y] == 2 && !isUsed[x][y]){
posBuffer = new Pos(x,y);
queueG.add(posBuffer);
isUsed[x][y] = true;
}
}
}
}
}
else if (paint[i][j] == 3 && !isUsed[i][j]) {
posBuffer = new Pos(i,j);
queueB.add(posBuffer);
numOfpaintB++;
while(!queueB.isEmpty()) {
tmpPos = queueB.poll();
for (int k = 0; k < dx.length; k++) {
x = tmpPos.pos_x + dx[k];
y = tmpPos.pos_y + dy[k];
if (-1 < x && x < N && -1 < y && y < N) {
if (paint[x][y] == 3 && !isUsed[x][y]){
posBuffer = new Pos(x,y);
queueB.add(posBuffer);
isUsed[x][y] = true;
}
}
}
}
}
else if (((paint[i][j] == 1) ||(paint[i][j] == 2)) && !isUsedGR[i][j]) {
posBuffer = new Pos(i, j);
queueRG.add(posBuffer);
numOfpaintRG++;
while (!queueRG.isEmpty()) {
tmpPos = queueRG.poll();
for (int k = 0; k < dx.length; k++) {
x = tmpPos.pos_x + dx[k];
y = tmpPos.pos_y + dy[k];
if (-1 < x && x < N && -1 < y && y < N) {
if (((paint[x][y] == 1) || (paint[x][y] == 2)) && !isUsedGR[x][y]) {
posBuffer = new Pos(x, y);
queueRG.add(posBuffer);
isUsedGR[x][y] = true;
}
}
}
}
}
}
}
System.out.println(numOfpaintR + numOfpaintG + numOfpaintB);
System.out.println(numOfpaintRG + numOfpaintB);
}
}이 아래 코드는 적록색약 조건을 그냥 따로 다시 한번더 구해주는 코드이기 떄문에 크게 다르지 않지만 다시한번 차이점을 파악해볼 필요가 있다. 추후 스터디에서 코드 리뷰후에 문제점을 추가해서 기입할 예정이다.
import java.io.*;
import java.util.*;
public class b10026 {
public static class Pos {
int pos_x;
int pos_y;
Pos(int x, int y) {
pos_x = x;
pos_y = y;
}
}
public static void main(String[] args) throws Exception {
int N;
int x;
int y;
int numOfpaintR = 0;
int numOfpaintG = 0;
int numOfpaintB = 0;
int numOfpaintRG = 0;
String stringBuffer;
int[][] paint;
boolean[][] isUsed;
boolean[][] isUsedGR;
char[] charBuffer ;
Queue<Pos> queueR = new LinkedList<>();
Queue<Pos> queueG = new LinkedList<>();
Queue<Pos> queueB = new LinkedList<>();
Queue<Pos> queueRG = new LinkedList<>();
Pos tmpPos;
Pos posBuffer;
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
paint = new int[N][N];
isUsed = new boolean[N][N];
isUsedGR = new boolean[N][N];
charBuffer = new char[N];
for (int i = 0; i < N; i++) {
stringBuffer = br.readLine();
for (int j = 0; j < N; j++) {
charBuffer[j] = stringBuffer.charAt(j);
if (charBuffer[j]== 'R') {
paint[i][j] = 1;
} else if (charBuffer[j] == 'G') {
paint[i][j] = 2;
} else if (charBuffer[j] == 'B') {
paint[i][j] = 3;
}
}
}
/*
//주어지는 입력이 String 한줄인데 착각으로 nextToken을 받으면 각으로 끝는걸 까먹음
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
if (st.nextToken() == "R") {
paint[i][j] = 1;
} else if (st.nextToken() == "G") {
paint[i][j] = 2;
} else if (st.nextToken() == "B") {
paint[i][j] = 3;
}
}
}
*/
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (paint[i][j] == 1 && !isUsed[i][j]) {
posBuffer = new Pos(i,j);
queueR.add(posBuffer);
numOfpaintR++;
while(!queueR.isEmpty()) {
tmpPos = queueR.poll();
for (int k = 0; k < dx.length; k++) {
x = tmpPos.pos_x + dx[k];
y = tmpPos.pos_y + dy[k];
if (-1 < x && x < N && -1 < y && y < N) {
if (paint[x][y] == 1 && !isUsed[x][y]){
posBuffer = new Pos(x,y);
queueR.add(posBuffer);
isUsed[x][y] = true;
}
}
}
}
}
else if (paint[i][j] == 2 && !isUsed[i][j]) {
posBuffer = new Pos(i,j);
queueG.add(posBuffer);
numOfpaintG++;
while(!queueG.isEmpty()) {
tmpPos = queueG.poll();
for (int k = 0; k < dx.length; k++) {
x = tmpPos.pos_x + dx[k];
y = tmpPos.pos_y + dy[k];
if (-1 < x && x < N && -1 < y && y < N) {
if (paint[x][y] == 2 && !isUsed[x][y]){
posBuffer = new Pos(x,y);
queueG.add(posBuffer);
isUsed[x][y] = true;
}
}
}
}
}
else if (paint[i][j] == 3 && !isUsed[i][j]) {
posBuffer = new Pos(i,j);
queueB.add(posBuffer);
numOfpaintB++;
while(!queueB.isEmpty()) {
tmpPos = queueB.poll();
for (int k = 0; k < dx.length; k++) {
x = tmpPos.pos_x + dx[k];
y = tmpPos.pos_y + dy[k];
if (-1 < x && x < N && -1 < y && y < N) {
if (paint[x][y] == 3 && !isUsed[x][y]){
posBuffer = new Pos(x,y);
queueB.add(posBuffer);
isUsed[x][y] = true;
}
}
}
}
}
}
}
System.out.println(numOfpaintR + numOfpaintG + numOfpaintB);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (((paint[i][j] == 1) ||(paint[i][j] == 2)) && !isUsedGR[i][j]) {
posBuffer = new Pos(i, j);
queueRG.add(posBuffer);
numOfpaintRG++;
while (!queueRG.isEmpty()) {
tmpPos = queueRG.poll();
for (int k = 0; k < dx.length; k++) {
x = tmpPos.pos_x + dx[k];
y = tmpPos.pos_y + dy[k];
if (-1 < x && x < N && -1 < y && y < N) {
if (((paint[x][y] == 1) || (paint[x][y] == 2)) && !isUsedGR[x][y]) {
posBuffer = new Pos(x, y);
queueRG.add(posBuffer);
isUsedGR[x][y] = true;
}
}
}
}
}
}
}
System.out.println(numOfpaintRG + numOfpaintB);
}
}
LIST
'알고리즘' 카테고리의 다른 글
| JAVA SWING GUI (With JDBC) 로그인 예제 프로그램 - 3. DB연결 (1) | 2023.07.24 |
|---|---|
| b1926.java 백준 그림 (0) | 2023.04.24 |
| b15649.java 백준 N과 M(1) (0) | 2023.04.04 |
| 백준 7569 토마토 - java (1) | 2023.03.26 |
| 7576 토마토 - java (0) | 2023.03.23 |
'알고리즘' Related Articles
more
