알고리즘/BOJ
10026. 적록색약
병인
2019. 10. 15. 19:29
https://www.acmicpc.net/problem/10026
10026번: 적록색약
문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은
www.acmicpc.net
<JAVA>
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class pos {
int x, y;
pos(int x, int y) {
this.x = x;
this.y = y;
}
}
class Main {
final static int dx[] = { 1, -1, 0, 0 };
final static int dy[] = { 0, 0, 1, -1 };
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int normal = 0, obstacle = 0;
int N = Integer.parseInt(br.readLine());
char[][] map = new char[N][N];
boolean[][] visit = new boolean[N][N];
for (int i = 0; i < N; ++i) {
map[i] = br.readLine().toCharArray();
}
// R(빨강), G(초록), B(파랑)
Queue<pos> q = new LinkedList<>();
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (!visit[i][j]) {
char now = map[i][j];
q.clear();
q.add(new pos(i, j));
++normal;
while (!q.isEmpty()) {
pos cur = q.poll();
for (int dir = 0; dir < 4; ++dir) {
int nx = cur.x + dx[dir];
int ny = cur.y + dy[dir];
if (nx < 0 || ny < 0 || nx >= N || ny >= N || visit[nx][ny] || map[nx][ny] != now)
continue;
visit[nx][ny] = true;
q.add(new pos(nx, ny));
}
}
}
}
}
visit = new boolean[N][N];
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (!visit[i][j]) {
char now = map[i][j];
q.clear();
q.add(new pos(i, j));
++obstacle;
while (!q.isEmpty()) {
pos cur = q.poll();
for (int dir = 0; dir < 4; ++dir) {
int nx = cur.x + dx[dir];
int ny = cur.y + dy[dir];
if (now == 'R' || now == 'G') {
if (nx < 0 || ny < 0 || nx >= N || ny >= N || visit[nx][ny] || map[nx][ny] == 'B')
continue;
visit[nx][ny] = true;
q.add(new pos(nx, ny));
} else {
if (nx < 0 || ny < 0 || nx >= N || ny >= N || visit[nx][ny] || map[nx][ny] != 'B')
continue;
visit[nx][ny] = true;
q.add(new pos(nx, ny));
}
}
}
}
}
}
System.out.println(normal + " " + obstacle);
}
}<C++>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
struct pos {
int x, y;
};
const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, 1, -1 };
char map[100][100];
bool visit[100][100];
int main()
{
cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
int normal = 0, obstacle = 0;
int N;
string s;
cin >> N;
for (int i = 0; i < N; ++i) {
cin >> s;
for (int j = 0; j < N; ++j)
{
map[i][j] = s[j];
}
}
// R(빨강), G(초록), B(파랑)
queue<pos> q;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (!visit[i][j]) {
char now = map[i][j];
q.push({ i, j });
++normal;
while (!q.empty()) {
pos cur = q.front(); q.pop();
for (int dir = 0; dir < 4; ++dir) {
int nx = cur.x + dx[dir];
int ny = cur.y + dy[dir];
if (nx < 0 || ny < 0 || nx >= N || ny >= N || visit[nx][ny] || map[nx][ny] != now)
continue;
visit[nx][ny] = true;
q.push({ nx, ny });
}
}
}
}
}
memset(visit, false, sizeof(visit));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (!visit[i][j]) {
char now = map[i][j];
q.push({ i, j });
++obstacle;
while (!q.empty()) {
pos cur = q.front(); q.pop();
for (int dir = 0; dir < 4; ++dir) {
int nx = cur.x + dx[dir];
int ny = cur.y + dy[dir];
if (now == 'R' || now == 'G') {
if (nx < 0 || ny < 0 || nx >= N || ny >= N || visit[nx][ny] || map[nx][ny] == 'B')
continue;
visit[nx][ny] = true;
q.push({ nx, ny });
}
else {
if (nx < 0 || ny < 0 || nx >= N || ny >= N || visit[nx][ny] || map[nx][ny] != 'B')
continue;
visit[nx][ny] = true;
q.push({ nx, ny });
}
}
}
}
}
}
cout << normal << " " << obstacle;
}