문제 링크
문제 풀이
- 위 문제는 dfs, bfs 두 가지 방법으로 모두 풀이가 가능하다.
- 적록색약이 아닌 사람은 R, G, B 모두 다르게 인식하지만, 적록색약인 사람은 R, G를 구분하지 못하므로, 입력 받은 리스트에서 G인 부분을 R로 바꾸어 새로운 리스트를 생성하였다.
- 방문 처리 리스트(visited)를 통해서 시작 위치를 방문하지 않았으면 함수(dfs, bfs)를 실행한다. 이때, 해당 함수는 시작 위치와 동일한 위치에 대해서만 방문 처리를 하게 된다. 이후 해당 과정이 끝나면, result 값을 1 증가하는데, 이는 같은 색으로 인식 하는 하나의 부분의 개수를 세는 것과 동일하다.
- 반복문이 모두 끝날 때까지 동일한 방법으로 방문 처리 후, 부분의 개수를 카운트하여 최종적으로 적록색약이 아닌 사람과, 적록색약인 사람이 보는 부분의 개수를 출력한다.
전체 코드
# dfs 풀이
import sys
sys.setrecursionlimit(10 ** 7)
def dfs(x, y, l, v):
v[x][y] = True
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n and not v[nx][ny] and l[x][y] == l[nx][ny]:
dfs(nx, ny, l, v)
n = int(sys.stdin.readline())
l = [list(sys.stdin.readline().strip()) for _ in range(n)]
l2 = [["R" if j == "G" else j for j in i] for i in l]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited1 = [[False] * n for _ in range(n)]
visited2 = [[False] * n for _ in range(n)]
res1 = 0
res2 = 0
for i in range(n):
for j in range(n):
if not visited1[i][j]:
dfs(i, j, l, visited1)
res1 += 1
if not visited2[i][j]:
dfs(i, j, l2, visited2)
res2 += 1
print(res1, res2)
# bfs 풀이
import sys
from collections import deque
def bfs(x, y, l, v):
queue = deque()
queue.append((x, y))
v[x][y] = True
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n and not v[nx][ny] and l[x][y] == l[nx][ny]:
v[nx][ny] = True
queue.append((nx, ny))
n = int(sys.stdin.readline())
l = [list(sys.stdin.readline().strip()) for _ in range(n)]
l2 = [["R" if j == "G" else j for j in i] for i in l]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited1 = [[False] * n for _ in range(n)]
visited2 = [[False] * n for _ in range(n)]
res1 = 0
res2 = 0
for i in range(n):
for j in range(n):
if not visited1[i][j]:
bfs(i, j, l, visited1)
res1 += 1
if not visited2[i][j]:
bfs(i, j, l2, visited2)
res2 += 1
print(res1, res2)
반응형
'Coding Test > BOJ' 카테고리의 다른 글
[백준/Python] 2343 기타 레슨 (2) | 2024.02.17 |
---|---|
[백준/Python] 2170 선 긋기 (0) | 2024.02.17 |
[백준/Python] 12904 A와 B (2) | 2024.02.14 |
[백준/Python] 2565 전깃줄 (2) | 2024.02.13 |
[백준/Python] 13335 트럭 (2) | 2024.02.12 |