1. Problem 📃
📚 출처 - 10026 - 적록색약
문제 설명
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
예를 들어, 그림이 아래와 같은 경우에
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.
출력
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
입출력 예
| 예제 입력 | 예제 출력 |
|---|---|
| 5 RRRBB GGBBB BBBRR BBRRR RRRRR | 4 3 |
2. Logic 👨🏫
Logic
일단 정상일때와 적록색약일때 각각 구해주었습니다.
1. 한번 탐색에 들어갈때마다cnt를 증가시킨 후, 탐색에 들어간 초기 문자와 같은거면 모두 방문처리
2. 그렇게 새롭게 들어가는 것마다cnt를 증가시켜주고 1번 작업을 반복해줍니다.
Logic - 적록색약
1.Red-Green을 구별하는 것이 의미가 없기 때문에 Green을 Red로 변환해줍니다.
2. 그리고 정상일때의 로직과 똑같이 작동하게 해주면 간단하게 해결 가능합니다.
3. Code 💻
1. 내가 푼 코드 😁
from collections import deque
import sys
input = sys.stdin.readline
def bfs(v, i, j):
queue = deque()
queue.append((v, i, j))
while queue:
tmp, x, y = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < N and 0 <= ny < N:
if visitied[nx][ny] == 0 and tmp == graph[nx][ny]: # 다르게 인식됨
queue.append((graph[nx][ny], nx, ny))
visitied[nx][ny] = 1
def bfs_c(v, i, j):
queue = deque()
queue.append((v, i, j))
while queue:
tmp, x, y = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < N and 0 <= ny < N:
if visitied2[nx][ny] == 0 and tmp == graph_c[nx][ny]: # 다르게 인식됨
queue.append((graph_c[nx][ny], nx, ny))
visitied2[nx][ny] = 1
N = int(input())
graph = [list(map(str, input().strip())) for _ in range(N)]
graph_c = graph[:]
visitied = [[0] * N for _ in range(N)]
visitied2 = [[0] * N for _ in range(N)]
cnt = 0
cnt2 = 0
# 탐색 범위 설정
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# 정상 check
for i in range(len(graph)):
for j, v in enumerate(graph[i]):
if visitied[i][j] == 0:
visitied[i][j] = 1
bfs(v, i, j)
cnt += 1
# 적록색맹
for i in range(len(graph_c)):
for j, v in enumerate(graph_c[i]):
if v == 'G':
graph_c[i][j] = 'R'
# 적록색맹 check
for i in range(len(graph_c)):
for j, v in enumerate(graph_c[i]):
if visitied2[i][j] == 0:
visitied2[i][j] = 1
bfs_c(v, i, j)
cnt2 += 1
print(cnt, cnt2)2. 불필요한 코드 삭제 😁
from collections import deque
import sys
input = sys.stdin.readline
def bfs(v, i, j):
queue = deque()
queue.append((v, i, j))
while queue:
tmp, x, y = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < N and 0 <= ny < N:
if visitied[nx][ny] == 0 and tmp == graph[nx][ny]: # 다르게 인식됨
queue.append((graph[nx][ny], nx, ny))
visitied[nx][ny] = 1
N = int(input())
graph = [list(map(str, input().strip())) for _ in range(N)]
visitied = [[0] * N for _ in range(N)]
cnt = 0
cnt2 = 0
# 탐색 범위 설정
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
for i in range(len(graph)):
for j, v in enumerate(graph[i]):
if visitied[i][j] == 0:
visitied[i][j] = 1
bfs(v, i, j)
cnt += 1
visitied = [[0] * N for _ in range(N)]
# 적록색맹
for i in range(len(graph)):
for j, v in enumerate(graph[i]):
if v == 'G':
graph[i][j] = 'R'
# 적록색맹 check
for i in range(len(graph)):
for j, v in enumerate(graph[i]):
if visitied[i][j] == 0:
visitied[i][j] = 1
bfs(v, i, j)
cnt2 += 1
print(cnt, cnt2)4. Feedback 📚
1. 복사..?
원래 처음에 정상일때 Graph와 적록색약 일 때 Graph_c로 나눠 작업하려 했습니다.
그래서 아래와 같이 코드 복사를 진행하고 작업했는데
Graph_c = Graph이렇게 작업하고 Graph_c의 경우 Red-Green의 값을 변환해줘야 되는데 이 작업중에 Graph 원본의 값까지 바뀌는 걸 보고 왜 바뀌지?? 하고 찾아봤는데 파이썬에서 저런 경우 값만을 가져오는 것이 아니라 원본의 주소값을 복사해와 값을 비교하는 것이라는 것을 알 수 있었습니다.
a = 5
b = a
print(a)
print(b)
print(id(a))
print(id(b))
>>> 5
>>> 5
>>> 140723434760112
>>> 140723434760112id 값이 동일한 것을 알 수 있습니다.
a = [5, 1, 2]
b = a[:]
print(a)
print(b)
print(id(a))
print(id(b))
>>> [5, 1, 2]
>>> [5, 1, 2]
>>> 2973042898304
>>> 2973042921984
a[:]와 같이 하게되면 id 값이 변경된 것을 알 수 있습니다.
a = [5, 1, 2]
b = a[:]
print(a)
print(b)
print(id(a[0]))
print(id(b[0]))
>>> [5, 1, 2]
>>> [5, 1, 2]
>>> 140723434760112
>>> 140723434760112하지만 앞서 두 번째 예처럼 겉 껍데기의 id는 바뀐것을 알 수 있었지만 현재의 예제를 보면
a[0]와 같이 내부적으로는 id 값이 동일한 것을 알 수 있다. 따라서 이 경우 내부의 값을 변경하게 되면 원본까지 같이 변경되는 아주 곤란한 상황을 볼 수 있습니다.
참고 자료 📩
