[BOJ] 10026. 적록색약 Python, Java

https://www.acmicpc.net/problem/10026

10026번: 적록색약

 

 

1. 해결방법

BFS로 해결했다. DFS보단 BFS가 훨씬 간단해 보인 단순한 이유;;

R과 G가 같은 것으로 판단하기 위해서 단순하게 2중 for문을 이용해서 R을 G로 바꾸고 BFS를 한번 더 돌렸다.
끝;; 너무 쉬움..

 

 

2. 정답코드

Python

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
maps = [list(map(str, input().strip())) for _ in range(N)]


dy, dx = (1, -1, 0, 0), (0, 0, 1, -1)


def bfs(y, x, v):
    q = deque()
    q.append((y, x))

    while q:
        ey, ex = q.popleft()
        for d in range(4):
            ny, nx = ey + dy[d], ex + dx[d]
            if 0 <= nx < N and 0 <= ny < N and chk[ny][nx] == False and maps[ny][nx] == v:
                chk[ny][nx] = True
                q.append((ny, nx))


answer = []
count = 0
chk = [[False] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if chk[i][j] == False:
            chk[i][j] = True
            bfs(i, j, maps[i][j])
            count += 1

answer.append(count)


chk = [[False] * N for _ in range(N)]
count = 0

for i in range(N):
    for j in range(N):
        if maps[i][j] == 'R':
            maps[i][j] = 'G'

for i in range(N):
    for j in range(N):
        if chk[i][j] == False:
            chk[i][j] = True
            bfs(i, j, maps[i][j])
            count += 1

answer.append(count)

print(' '.join(map(str, answer)))

 

Java

package BFS;

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static char[][] maps;
    static boolean[][] chk;
    static int count;
    static int[] answer = new int[2];
    static String s;
    static Queue<Point> q;
    static int[] dy = {1, -1, 0, 0};
    static int[] dx = {0, 0, 1, -1};

    static void bfs(int y, int x, char v) {
        q = new LinkedList<>();
        q.offer(new Point(y, x));

        while (! q.isEmpty()) {
            Point now = q.poll();
            for (int d = 0; d < 4; d++) {
                int ny = now.x + dy[d];
                int nx = now.y + dx[d];
                if (ny < 0 || nx < 0 || ny >= N || nx >= N || chk[ny][nx]) continue;
                if (maps[ny][nx] == v) {
                    chk[ny][nx] = true;
                    q.offer(new Point(ny, nx));
                }
            }

        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        maps = new char[N][N];
        chk = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            s = br.readLine();
            for (int j = 0; j < N; j++) {
                maps[i][j] = s.charAt(j);
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (! chk[i][j]) {
                    chk[i][j] = true;
                    bfs(i, j, maps[i][j]);
                    count++;
                }
            }
        }
        answer[0] = count;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (maps[i][j] == 'R') maps[i][j] = 'G';
            }
        }
        count = 0;
        chk = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (! chk[i][j]) {
                    chk[i][j] = true;
                    bfs(i, j, maps[i][j]);
                    count++;
                }
            }
        }
        answer[1] = count;

        System.out.println(answer[0] + " " + answer[1]);
    }
}