[백준-10026] 적록색약

문제

링크

코드

적록색약인 사람과 아닌 사람이 봤을 때의 구역의 수를 한 번에 계산하려고 코드를 작성했다.
문제의 예제와 다른 분들이 올려주신 반례를 모두 돌렸을 때도 정답이라 뜨는데 제출만 하면 9%에서 실패해서 그냥 따로 계산했더니 맞았다.
일단 n의 범위가 1~100이라 시간이 많이 소요가 안됐기 때문에 맞춘 거 같다...
무엇이 잘못 됐을까 !!!!!!!!!!!!!1

성공 코드

from collections import deque
import sys
input = sys.stdin.readline

n =int(input())
graph = []

for _ in range(n) :
    graph.append(list(input()))

# 적록색약이 아닌 사람이 봤을 때 구역의 수
def count1() :
    visited = [[0] * n for _ in range(n)]
    tmp = ''
    count = 0
    for i in range(n) :
        for j in range(n) :
            queue = deque()
            if visited[i][j] == 0 :
                visited[i][j] = 1
                tmp = graph[i][j]
                # 초록이나 빨간색인 경우 하나의 문자로 바꿔준다.
                if graph[i][j] in ('G', 'R') :
                    graph[i][j] = 'G'
                queue.append([i, j])
                while queue :
                    p, q = queue.popleft()
                    for a, b in ([-1, 0], [1, 0], [0, 1], [0, -1]) :
                        if 0 <= p+a < n and 0 <= q+b < n :
                            if tmp == graph[p+a][q+b] and visited[p+a][q+b] == 0 :
                                visited[p+a][q+b] = 1
                                queue.append([p+a, q+b])
                                if tmp in ('G', 'R') :
                                    graph[p+a][q+b] = 'G'
                count += 1
    print(count, end=" ")

count1()

# 적록색약인 사람이 봤을 때 구역의 수
def count2() :
    visited = [[0] * n for _ in range(n)]
    tmp = ''
    count = 0
    for i in range(n) :
        for j in range(n) :
            queue = deque()
            if visited[i][j] == 0 :
                visited[i][j] = 1
                tmp = graph[i][j]
                queue.append([i, j])
                while queue :
                    p, q = queue.popleft()
                    for a, b in ([-1, 0], [1, 0], [0, 1], [0, -1]) :
                        if 0 <= p+a < n and 0 <= q+b < n :
                            if tmp == graph[p+a][q+b] and visited[p+a][q+b] == 0 :
                                visited[p+a][q+b] = 1
                                queue.append([p+a, q+b])
                count += 1
    print(count)

count2()

• 코드 길이 줄인 코드

from collections import deque
import sys
input = sys.stdin.readline

n =int(input())
graph = []

for _ in range(n) :
    graph.append(list(input()))

def bfs(i, j) :
    queue = deque()
    visited[i][j] = 1
    tmp = graph[i][j]
    queue.append([i, j])
    while queue :
        p, q = queue.popleft()
        for a, b in ([-1, 0], [1, 0], [0, 1], [0, -1]) :
            if 0 <= p+a < n and 0 <= q+b < n :
                if tmp == graph[p+a][q+b] and visited[p+a][q+b] == 0 :
                    visited[p+a][q+b] = 1
                    queue.append([p+a, q+b])
                    if graph[p+a][q+b] == 'R' :
                        graph[p+a][q+b] = 'G'
    return 1
    
# 적록색약이 아닌 사람
visited = [[0] * n for _ in range(n)]
count = 0    
for i in range(n) :
    for j in range(n) :
        if visited[i][j] == 0 :
            count += bfs(i, j)
            if graph[i][j] == 'R' :
                graph[i][j] = 'G'
print(count, end=" ")        

# 적록색약인 사람
visited = [[0] * n for _ in range(n)]
count = 0    
for i in range(n) :
    for j in range(n) :
        if visited[i][j] == 0 :
            count += bfs(i, j)
print(count, end=" ")        

코드 길이가 너무 길어서 dfs를 하나로 만들어 작성했다.

실패 코드

from collections import deque
import sys
input = sys.stdin.readline

n =int(input())
graph = []
visited = [[0] * n for _ in range(n)]

for _ in range(n) :
    graph.append(list(input()))

# 1번이 적록색약이 아닌 사람, 2번은 적록색약인 사람
count_1 = 0
count_2 = 0
tmp = ''
for i in range(n) :
    for j in range(n) :
        if visited[i][j] == 0 :
            visited[i][j] = 1
            tmp = graph[i][j]
            # 적록색약인 경우에만
            # R, G일 때, 이미 방문했던 구역이 R, G이라면 1을 빼준다.
            if graph[i][j] in ('R', 'G') :
                for x, y in ([-1, 0], [1, 0], [0, 1], [0, -1]) : 
                    if 0 <= i+x < n and 0 <= j+y < n :
                        if graph[i+x][j+y] in ('R', 'G') and visited[i+x][j+y] == 1 :
                            count_2 -= 1
                            break
            queue = deque()
            queue.append([i, j])
            while queue :
                p, q = queue.popleft()
                for a, b in ([-1, 0], [1, 0], [0, 1], [0, -1]) :
                    if 0 <= p+a < n and 0 <= q+b < n :
                        if tmp == graph[p+a][q+b] and visited[p+a][q+b] == 0 :
                            visited[p+a][q+b] = 1
                            queue.append([p+a, q+b])
            count_1 += 1
            count_2 += 1
            print(count_1, count_2)
print(str(count_1), str(count_2))

다른 분들의 코드를 살펴봤는데 대부분 dfs를 두 번 사용해서 푸신 분들이 많았다.
그냥 원래 이렇게 푸는 문제인 거 같아서 넘어감 ~~