<BOJ>10026번: 적록색약
문제
접근
- BFS 코드 틀을 알고 있으면 쉽게 풀 수 있는 전형적인 BFS 문제이다.
- 현재 좌표와 다음 좌표의 색상이 같으면 이동하는 방식으로 탐색한다.
- 2중 for문으로 방문하지 않은 좌표인지 파악해서 해당 좌표에서 BFS를 호출한다. 이 때 카운팅을 한다. → 각 색상별로 영역이 몇 개인지 파악함
- 적록색약인 경우를 위해 G영역을 R영역으로 바꾸고, visited를 초기화 한 뒤 다시 탐색한다.
내 코드
from collections import deque
def bfs(x, y):
q.append((x, y))
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
visited[x][y] = True
while q:
x, y = q.popleft()
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == grid[x][y] and not visited[nx][ny]:
visited[nx][ny] = True
q.append((nx, ny))
n = int(input())
grid = [list(input()) for _ in range(n)]
q = deque()
visited = [[False] * n for _ in range(n)]
count = 0
for i in range(n):
for j in range(n):
if not visited[i][j]:
bfs(i, j)
count += 1
for i in range(n):
for j in range(n):
if grid[i][j] == 'G':
grid[i][j] = 'R'
visited = [[False] * n for _ in range(n)]
blind = 0
for i in range(n):
for j in range(n):
if not visited[i][j]:
bfs(i, j)
blind += 1
print(count, blind)
Author And Source
이 문제에 관하여(<BOJ>10026번: 적록색약), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@songs4805/BOJ10026번-적록색약
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
from collections import deque
def bfs(x, y):
q.append((x, y))
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
visited[x][y] = True
while q:
x, y = q.popleft()
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == grid[x][y] and not visited[nx][ny]:
visited[nx][ny] = True
q.append((nx, ny))
n = int(input())
grid = [list(input()) for _ in range(n)]
q = deque()
visited = [[False] * n for _ in range(n)]
count = 0
for i in range(n):
for j in range(n):
if not visited[i][j]:
bfs(i, j)
count += 1
for i in range(n):
for j in range(n):
if grid[i][j] == 'G':
grid[i][j] = 'R'
visited = [[False] * n for _ in range(n)]
blind = 0
for i in range(n):
for j in range(n):
if not visited[i][j]:
bfs(i, j)
blind += 1
print(count, blind)
Author And Source
이 문제에 관하여(<BOJ>10026번: 적록색약), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@songs4805/BOJ10026번-적록색약저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)