https://www.acmicpc.net/problem/10026
10026번: 적록색약
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 적록색약을 가진 분들과 적록색약이 아닌 분들이 보는 것이 다르다는 것을 이용한 문제입니다.
그것을 제외하고는 일반적인 bfs 문제와 같습니다. 예시를 들면 다음과 같습니다.
위의 그림이 있을 때 적록색약이 아닌 분들은 R, G, B로 3가지 구역, 적록색약인 분들은 RG, B로 2가지 구역으로 보는 것입니다. 따라서 이 점에 유의하며 bfs를 구현하면 됩니다.
문제 해결을 위한 팁
저의 경우는 그래프를 2개로 하여 기존에 입력받은 그래프를 복사하여 사용하였습니다. 이를 copy를 이용하였는데 copy의 경우 shallow copy, deep copy가 존재합니다. shallow copy의 경우 원본 혹은 복사본을 수정할 경우 기존의 그래프 역시 수정이 되므로 deep copy를 사용하여야 합니다. 따라서 import copy, 원본 = copy.deepcopy(복사본)를 사용합니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
from collections import deque
import copy
def bfs(graph, i, j):
q = deque()
q.append((i, j))
target = graph[i][j]
graph[i][j] = 'a'
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= n:
continue
if graph[nx][ny] == target:
graph[nx][ny] = 'a'
q.append((nx, ny))
def bfs2(graph, i, j):
q = deque()
q.append((i, j))
target = graph[i][j]
graph[i][j] = 'a'
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= n:
continue
if target == 'R' or target == 'G':
if graph[nx][ny] == 'R' or graph[nx][ny] == 'G':
graph[nx][ny] = 'a'
q.append((nx, ny))
else:
if graph[nx][ny] == target:
graph[nx][ny] = 'a'
q.append((nx, ny))
n = int(input())
graph = [['a'] * n for _ in range(n)]
for i in range(n):
inputData = list(input())
for j in range(n):
graph[i][j] = inputData[j]
graph2 = copy.deepcopy(graph)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
count = 0
for i in range(n):
for j in range(n):
if graph[i][j] != 'a':
bfs(graph, i, j)
count += 1
print(count, end=" ")
count = 0
for i in range(n):
for j in range(n):
if graph2[i][j] != 'a':
bfs2(graph2, i, j)
count += 1
print(count)
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 1003번: 피보나치 함수(Python) (0) | 2022.01.19 |
|---|---|
| 백준 알고리즘 7569번: 토마토(Python) (0) | 2022.01.15 |
| 백준 알고리즘 4963번: 섬의 개수(Python) (0) | 2022.01.15 |
| 백준 알고리즘 18870번: 좌표 압축(Python) (0) | 2022.01.14 |
| 백준 알고리즘 7576번: 토마토(Python) (0) | 2022.01.14 |