[파이썬/Python] 백준 10026번 적록색약

[파이썬/Python] 백준 10026번 적록색약

10026번: 적록색약

---

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

 

해설

상하좌우를 체크해서 같은 컬러가 아닐 경우 영역을 구분해주는 간단한 DFS 문제라고 생각했다.

문제인 부분은 적록색약을 어떻게 처리해줄 것인가?

 

처음엔 모두 구분해준다음, 그리드 하나를 또 deepcopy 하여 조건문으로 red 와 green 일 경우 함께 처리해줄까 생각했지만..

코드 중복이 너무 많을 것 같고 너무 비효율적인 것 같아 아이디어가 필요했다.

( 실제로 deepcopy 로 풀었을 때 메모리초과 발생 )

 

1. DFS를 통해 영역의 개수를 구한다. ( => 적록색맹이 아닐 때 )

2. G를 R로 치환한다.

3. DFS를 통해 영역의 개수를 구한다. ( => 적록색맹일 때 )

 

코드

import sys
sys.setrecursionlimit(1000000)

N = int(sys.stdin.readline())
grid = [list(sys.stdin.readline().rstrip()) for _ in range(N)]
visited = [[False] * N for _ in range(N)]

d = [(0,1), (0, -1), (1,0), (-1,0)]
def dfs(x, y):
    visited[y][x] = True
    color = grid[y][x]
    for dx, dy in d:
        X, Y = x + dx, y + dy
        if (0 <= X < N) and (0 <= Y < N):
            if visited[Y][X] == False and grid[Y][X] == color:
                dfs(X, Y)
            
cnt, cnt2 = 0, 0

for y in range(N):
    for x in range(N):
        if visited[y][x] == False:
            dfs(x,y)
            cnt += 1

for y in range(N):
    for x in range(N):
        if grid[y][x] == 'G':
            grid[y][x] = 'R'
visited = [[False] * N for _ in range(N)]

for y in range(N):
    for x in range(N):
        if visited[y][x] == False:
            dfs(x,y)
            cnt2 += 1

print(cnt, cnt2)

 

풀이

import sys
sys.setrecursionlimit(1000000)

N = int(sys.stdin.readline())
grid = [list(sys.stdin.readline().rstrip()) for _ in range(N)]
visited = [[False] * N for _ in range(N)]

1. 입력을 받는 부분이다. 색을 리스트에 하나씩 넣어야 하기 때문에 붙여진 문자열을 잘라주어야한다.

list 메서드는 문자열을 한글자씩 잘라준다.

이 때, rstrip() 을 통해 공백을 제거하지 않으면 "\n" 도 함께 리스트에 추가되니 주의하자.

문자열(string)을 한 글자씩 끊어서 리스트로 바꾸기

 

리스트 공백 제거하기(\n, 스페이스, 탭)

 

 

d = [(0,1), (0, -1), (1,0), (-1,0)]
def dfs(x, y):
    visited[y][x] = True
    color = grid[y][x]
    for dx, dy in d:
        X, Y = x + dx, y + dy
        if (0 <= X < N) and (0 <= Y < N):
            if visited[Y][X] == False and grid[Y][X] == color:
                dfs(X, Y)

2. DFS 함수이다.

유의해야되는 부분은, 색을 따로 변수로 저장하여 이동할 칸의 색과 비교해보아야 한다.

 

 

cnt, cnt2 = 0, 0

for y in range(N):
    for x in range(N):
        if visited[y][x] == False:
            dfs(x,y)
            cnt += 1

3. 적록색맹이 아닐 경우를 먼저 구한다.

 

for y in range(N):
    for x in range(N):
        if grid[y][x] == 'G':
            grid[y][x] = 'R'
visited = [[False] * N for _ in range(N)]

4. 그리드의 초록을 빨강으로 수정해준다.

주의할 점은, 방문 리스트가 다시 사용되기 때문에 초기화해야한다.

 

for y in range(N):
    for x in range(N):
        if visited[y][x] == False:
            dfs(x,y)
            cnt2 += 1
            
 print(cnt, cnt2)

5. 적록색맹일 경우를 구한다.

 

피드백

좋은 프로그래머에 대한 현업 개발자의 인터뷰 영상을 얼마전에 본적이 있다.

코딩 능력보다는 "문제해결 능력"을 길러야 한다고 말한다.

"G를 R로 바꾼다는 매우 간단한 아이디어" 하나로 이 문제는 매우 쉽게 풀 수 있다.

그러나 그 아이디어를 알기 전까진 어떻게 효율적으로 해결할 수 있을지 감도 잡지 못했다.

창의력은 어떻게 기를 수 있을까.ㅠ

코드 중복 또한 줄일 방법은 없을까