[백준] 10026번 적록색약
https://www.acmicpc.net/problem/10026
문제설명 📖
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
예를 들어, 그림이 아래와 같은 경우에
적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.
출력
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
입출력 예
문제접근 💡
** 1. BFS구현
2. 적록색약과 적록색약이 아닌 경우 두 경우의 함수와 방문행렬을 따로 만들었다.
3. 적록색약인 경우 matrix[x][y] == 'R' and matrix[nx][ny] == 'G'와 그 반대인 경우도 방문하는 것으로 코드를 작성했다.
문제풀이 💡
import sys
from collections import deque
n = int(input())
matrix = [list(map(str, sys.stdin.readline())) for _ in range(n)]
# 방문행렬
visited1 = [[0]*n for _ in range(n)]
visited2 = [item[:] for item in visited1]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
queue = deque()
def noseakyak():
while queue:
x,y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx<0 or nx>=n or ny<0 or ny>=n:
continue
if matrix[x][y] == matrix[nx][ny] and visited1[nx][ny] == 0:
queue.append((nx,ny))
visited1[nx][ny] = 1
def seakyak():
while queue:
x,y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx<0 or nx>=n or ny<0 or ny>=n:
continue
if visited2[nx][ny] == 0:
if matrix[x][y] == matrix[nx][ny] or matrix[x][y] == 'R' and matrix[nx][ny] == 'G' or matrix[x][y] == 'G' and matrix[nx][ny] == 'R':
queue.append((nx,ny))
visited2[nx][ny] = 1
cnt1 = 0
cnt2 = 0
for i in range(n):
for j in range(n):
if visited1[i][j] == 0:
queue.append((i,j))
visited1[i][j] = 1
noseakyak()
cnt1 += 1
if visited2[i][j] == 0:
queue.append((i,j))
visited2[i][j] = 1
seakyak()
cnt2 += 1
print(cnt1, cnt2)문제팁 💡
구현은 간단했으나 def saekyak함수에서 index오류가 났다. 인덱스 범위를 초과했다는 것이었다.
바로 문자열을 입력받을 때 오류가 발생했던 것이다.
내가 짠 코드는 [[R,R,B,B,G],...]이런식으로 짰을 경우로 작성한 코드인데
입력받을 때 split()함수를 써서 [[RRBBG],...] 이런식으로 배열이 만들어진 것이다.
string.split(separator, limit)
split()은 구분자 함수로 파라미터를 입력해주지 않으면 문자열 전체를 담아 리턴한다.
이 문제는 공백없이 RRRBB와 같이 입력되므로 split을 쓰면 RRRBB 문자열 전체를 담아 리턴하므로 나와 같은 코드에서는 split()을 써주면 안된다.
다른풀이 💡
나와 기본적인 구조는 같지만, 함수와 방문행렬을 하나만 만들어 코드를 짠 경우이다.
적록색약인 경우 'R'을 'G'로 바꿔서 배열을 미리 처리해주었다.
재사용성이 좋은 함수로 훨씬 효율적이고 직관적이다.
from collections import deque
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def bfs(x, y):
q.append([x, y])
c[x][y] = cnt
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n:
if a[nx][ny] == a[x][y] and c[nx][ny] == 0:
q.append([nx, ny])
c[nx][ny] = 1
n = int(input())
a = [list(map(str, input())) for _ in range(n)]
c = [[0]*n for _ in range(n)]
q = deque()
cnt = 0
for i in range(n):
for j in range(n):
if c[i][j] == 0:
bfs(i, j)
cnt += 1
print(cnt, end=' ')
for i in range(n):
for j in range(n):
if a[i][j] == 'R':
a[i][j] = 'G'
c = [[0]*n for _ in range(n)]
cnt = 0
for i in range(n):
for j in range(n):
if c[i][j] == 0:
bfs(i, j)
cnt += 1
print(cnt)