10026 적록색약 _python

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

10026번: 적록색약

색약이 있어도 사는데 지장없다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

문제를 보자말자 떠오른게 플러드필 2번쓰면 되겠다 싶었다.

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%9F%AC%EB%93%9C_%ED%95%84

플러드 필 - 위키백과, 우리 모두의 백과사전

색칠하는 알고리즘. 몰라도 BFS나 DFS응용이라고 생각하면 되고, 쉽게 떠올릴 수 있는 방법.

 

너무 쉽게 떠오르는데 골드라서 시간초과가 날줄알고 방문을 한번 탐색에서 방문체크를 두개 동시에 해야할 줄알았으나,

구현하면 너무 복잡하게 코드가 그려질거 같아서 그냥 코드를 만들어봤다.

의외로 빠른속도가 나왔다. ^ㅇ^

색약이 아닌 사람의 답과 색약인 사람의 답을 따로 1번씩 해주면 끝이다.

 

필자는 함수로 안만들고 그냥 복붙으로 깡구현했다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

import sys
input = sys.stdin.readline

"""
플러드 필 2번
"""

N = int(input())
color = [input().rstrip() for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[False] * N for i in range(N)] 
list = []
ans = 0

for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            list.append((i,j))
            visited[i][j] = True
            curColor = color[i][j]

            while list:
                x, y = list.pop()
                for k in range(4):
                    xi = x + dx[k]
                    yi = y + dy[k]
                    if 0<=xi<N and 0<=yi<N and not visited[xi][yi] and color[xi][yi] == curColor:
                        visited[xi][yi] = True
                        list.append((xi,yi))
            ans += 1

print(ans, end=" ")
        
visited = [[False] * N for i in range(N)] 
list = []
ans = 0
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            list.append((i,j))
            visited[i][j] = True
            curColor = color[i][j]
            if curColor == "B":
                while list:
                    x, y = list.pop()
                    for k in range(4):
                        xi = x + dx[k]
                        yi = y + dy[k]
                        if 0<=xi<N and 0<=yi<N and not visited[xi][yi] and color[xi][yi] == "B":
                            visited[xi][yi] = True
                            list.append((xi,yi))
                ans += 1
            else:
                while list:
                    x, y = list.pop()
                    for k in range(4):
                        xi = x + dx[k]
                        yi = y + dy[k]
                        if 0<=xi<N and 0<=yi<N and not visited[xi][yi] and color[xi][yi] != "B":
                            visited[xi][yi] = True
                            list.append((xi,yi))
                ans += 1

print(ans, end=" ")

68ms

python에서 2등 키야