10026번/ BFS 적록색약/ 파이썬

📕 문제

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

 

📗실행결과

 

 

📄 풀이

1. 적록색맹 아닐 때 ) DFS로 영역 개수 구하기 

2. G-> R로 바꾸기

3. 적록생맹일 때) DFS로 영역 개수 수하기

 

 

💻 답안

  import sys
sys.setrecursionlimit(10**6)

# from collections import deque


n = int(sys.stdin.readline())
# list 메서드로 문자열 하나씩 잘라줌, rstrip으로 \n제거
grid = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
# 방문표시할 배열 false로 초기화
visited = [[False]* n for _ in range(n)]

# 상하좌우 요소 탐색
d = [(0,1),(0,-1),(1,0),(-1,0)]

def dfs(x,y):
     visited[y][x] = True
     color = grid[y][x]
     for dx, dy in d:
          X, Y = x + dx, y +dy
          if(0 <= X < n) and (0 <= Y < n):
               if visited[Y][X] == False and grid[Y][X] == color:
                    dfs(X,Y)

#적록색약이 아닌 경우
cnt, cnt2 = 0,0

for y in range(n):
    for x in range(n):
         if visited[y][x] == False:
              dfs(x,y)
              cnt += 1

# 그리드의 초록=>빨강 수정, 방문 리스트 재사용위해 초기화하기
for  y in range(n) :
     for x in range(n):
          if grid[y][x] == 'G':
            grid[y][x] = 'R'

visited = [[False] * n for _ in range(n)]

#적록색맹인 경우
for y in range(n):
     for x in range(n):
          if visited[y][x] == False:
               dfs(x,y)
               cnt2 += 1
print(cnt, cnt2)

 

☺️ BFS 문제 자주 실수하는 점

1. 시작점에 방문했다는 표시를 남기지 않는다.

=> 시작점을 두번 방문할 수 있음

 

2. 큐에 넣을 때. 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문했다는 표시를 남김

=> 같은 칸이 큐에 여러 번들어가서 시간 초과 or 메모리 초과 발생

 

3. 이웃한 원소가 범위를 벗어났는지에 대한 체크 잘못함

 

☺️ DFS 문제 풀 때 참고

1. 시작하는 칸에 스택에 넣고 방문 표시 남기기

2. 스택에서 원소 꺼내서 그 칸과 상하좌우로 인접한 칸에 대해 3번 진행하기

3. 해당 칸을 이전에 방문했으면 아무것도 하지 않고, 처음 방문했으면 방문 표시 남기고 해당 칸을 스택에 삽입

4. 스택 빌 때까지 2번 반복

모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 n개일 때 O(n)

 

😉 참고

 

https://chaewonkong.github.io/posts/python-deque.html

Python - 데크(deque) 언제, 왜 사용해야 하는가?

 

https://www.youtube.com/watch?v=93jy2yUYfVE&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=11

 

https://develop247.tistory.com/248

[파이썬/Python] 백준 10026번 적록색약