on
[백준] 자바 10026 적록색약
[백준] 자바 10026 적록색약
문제
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
예를 들어, 그림이 아래와 같은 경우에
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.
출력
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
테스트 케이스
입력 1
1
G
출력 1
1 1
입력 2
3
RGB
RGB
RGB
출력 2
3 2
입력 3
3
RRR
RRR
RRR
출력 3
1 1
접근
일반적인 BFS문제와 아주 유사하지만, 적녹색약과 정상인의 BFS를 따로 적용하는 게 포인트인 것 같습니다.
정상인의 bfs를 수행한 후, 사용하던 맵의 R를 G로 바꿔주거나, G를 R로 바꿔주면 색약이 보는 맵으로 BFS를 돌릴 수 있습니다.
코드
import java.util.*; import java.io.*; import java.text.SimpleDateFormat; class Node{ int x; int y; public Node(int x,int y) { this.x = x; this.y = y; } } class Main { static int n, count, count2; static char map[][]; static boolean visit[][]; static int dx[] = {-1,1,0,0}; static int dy[] = {0,0,-1,1}; static void bfs(int x, int y) { Queue q = new LinkedList<>(); q.add(new Node(x,y)); visit[x][y] = true; while(!q.isEmpty()) { Node node = q.poll(); int x1 = node.x; int y1 = node.y; for(int i=0; i<4; i++) { int nx = x1 + dx[i]; int ny = y1 + dy[i]; if(nx>=0 && nx=0 && ny
주의
큐에 추가할때마다 VISIT배열을 TRUE로 변경해줄 것.
잘못하면 메모리초과남
728x90
반응형
from http://kjs-dev.tistory.com/171 by ccl(A) rewrite - 2021-11-03 05:28:00