[백준]10026번: 적록색약

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

10026번: 적록색약

---

 

1. 일반인 기준으로 bfs쫙 돌려서 구역이 몇 개인지 계산하여 출력한다.

 

2. 적록색약 기준으로 bfs를 다시 한 번 돌리기 위해 그래프를  살짝 변경해줬다.

 -그래프 모든 요소들을 비방문처리

 -모든 G를 R로 바꿔줬다 (적록색약은 G와 R을 구별 못하니 하나로 통일시킴)

 

3. 적록색약 기준으로 bfs 한 번 더 돌려서 결과 출력

---

BFS로 연결요소 개수 구한 방식

 

 -최초방문시에 bfs로 인접한 칸들을 모두 방문하고 True를 리턴

 -방문처리가 이미 된 칸이면 False를 리턴

 -bfs리턴값이 true일 때에만 count를 증가시킨다.

 

방문처리 방식

 -그래프 값이 대문자라면 방문한적 없는 칸이다. 소문자로 바꿔줌으로써 방문처리함

 -그래프 값이 소문자라면 방문한 적 있는 칸이다.

 

from collections import deque

dx=[-1,1,0,0]
dy=[0,0,-1,1]

def bfs(x,y):
  if graph[x][y].islower(): #방문한적있으면
    return False

  graph[x][y] = graph[x][y].lower() #방문처리
  q = deque()
  q.append((x,y))

  while q:
    a,b = q.popleft()
    for i in range(4):
      nx = a + dx[i]
      ny = b + dy[i]

      #범위내에 속하고 방문할 수 있고 방문한 적 없는 칸일경우
      if 0<=nx<n and 0<=ny<n and graph[nx][ny]==graph[a][b].upper() and graph[nx][ny].isupper():
        graph[nx][ny] = graph[nx][ny].lower() #방문처리
        q.append((nx,ny))
      
  return True



#입력받기
n = int(input())

graph=[]
for i in range(n):
  arr = []
  temp=input()
  for j in range(n):
    arr.append(temp[j])
  graph.append(arr)


#일반인 결과 출력
cnt1 = 0
for i in range(n):
  for j in range(n):
    if bfs1(i,j)==True:
      cnt1 += 1
print(cnt1,end=' ')

#그래프 비방문처리 & Red와 Green을 같은문자로 통일
for i in range(n):
  for j in range(n):
    graph[i][j] = graph[i][j].upper()
    if graph[i][j] == 'G':
      graph[i][j] = 'R'
    
#적록색약 결과 출력
cnt2 = 0
for i in range(n):
  for j in range(n):
    if bfs(i,j)==True:
      cnt2 += 1
print(cnt2)