DFS로 10문제 정도 풀어보니까 이제 어느정도 DFS 문제를 보면 어떻게 풀어야할지 감이 온다
이렇게 색칠해서 보니까 확 이해가 되었는데
백준 16173 점프왕쩰리, 1012 유기농 배추, 21736 헌내기 친구, 2667 단지번호
문제들처럼 현재 위치에서 위아래양옆을 탐색하는 방식이랑 비슷하다
골드문제라 그런지 탐색 조건이 좀 더 추가된 느낌?!?!
def DFS(x, y):
if x <= -1 or y >= n or x >= n or y <= -1: return False
else:
if graph[x][y] == 1: # 방문하지 않은곳
graph[x][y] = 0 # 방문처리
DFS(x - 1, y)
DFS(x + 1, y)
DFS(x, y + 1)
DFS(x, y - 1)DFS 상하좌우의 기본 베이스인 먼저
1. 입력받은 x, y가 배열을 벗어나는지 검사하고,
2. 벗어나지 않으면 방문한 곳인지 검사했다
3. 방문하지 않은 곳이면, 방문처리를 해주고 상하좌우 탐색 시작
하는 방식을 적용했다
방식 1 깊은 복사
여기서 이제 적록색맹이 아닌 graph와 적록색맹인 graph를 따로 만들어줘야 된다고 생각해서 깊은복사로 각각 2차원 배열을 생성해줬다.
이때 X_graph = graph, O_graph = graph 이런식으로 만들고 graph[x][y] = 0 으로 방문처리를 해주면 O_graph의 내용도 바껴버린다... 당연히 안바뀌겠지하고 저렇게 했다가 출력값이 4 0 나와가지고 혼자 막 당황함 ㅋㅋㅋㅋㅋㅋ
import copy
X_graph = copy.deepcopy(arr)
O_graph = copy.deepcopy(arr)
for x in range(0, n):
for y in range(0, n):
if(O_graph[x][y] == 'G'): O_graph[x][y] = 'R'
no_cnt = 0
yes_cnt = 0이렇게 깊은복사로 입력받은 arr를 복사해주고
적록색맹이 있는 graph에다가는 G의 값을 R로 바꿔줬다
visited 배열을 따로 만들어서 하는 방식은 visited 배열을 꼭 하나 더 만들어야할 필요가 있나? 라는 생각이 들어서 따로 생성하지 않고 현재 탐색한 위치의 좌표값을 0으로 바꿔주는 방식을 선택했다
def DFS(x, y, graph, v):
if x >= n or x <= -1 or y >= n or x <= -1 or graph[x][y] == 0: return False
else:
if(v == graph[x][y]):
graph[x][y] = 0 # visited
DFS(x+1, y, graph, v)
DFS(x-1, y, graph, v)
DFS(x, y+1, graph, v)
DFS(x, y-1, graph, v)기본 베이스에서 if문 조건이랑 함수 파라미터만 바꿔줬는데
들어온값이 이미 방문했는지 확인을 해줬고
현재 위치에서 그 전에 방문했던곳이랑 색상이 같은지 다른지 비교해줘야된다고 생각해서
v 파라미터가 바로 전에 방문한 곳의 색상 값을 나타내도록 만들었고
graph는 X_graph랑 O_graph 각각 DFS를 진행해야해서 선언해줬다
( visited 배열을 사용하면 graph 파라미터는 필요없을듯!! )
v 파라미터가 바로 전에 방문한 곳의 색상 값이기 때문에 현재 위치인 graph[x][y]와 값을 비교해서
같으면 계속 탐색해야하므로 해당 위치를 방문처리해주고 상하좌우로 탐색해줬다
만약 여기서 다르면 영역이 다르니까 cnt += 1을 해줘야 된다고 생각했고
DFS에서 영역의 개수 구하는 방식에서는 for문을 돌려서 거기서 += 1 해주는 방식을 사용한것처럼 동일하게 적용했다
for i in range(0, n):
for j in range(0, n):
# 적록색맹 없음
if X_graph[i][j] != 0:
DFS(i,j,X_graph, X_graph[i][j])
no_cnt += 1
# 적록색맹 있음
if O_graph[i][j] != 0:
DFS(i, j, O_graph, O_graph[i][j])
yes_cnt += 1대신에 방문하지 않은 곳에서만 DFS를 진행할 수 있도록 조건을 걸어주었다
코드 전체 (깊은 복사 사용한 방식)
import copy
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n = int(input())
arr = []
for _ in range(n):
arr.append(list(input()))
X_graph = copy.deepcopy(arr)
O_graph = copy.deepcopy(arr)
for x in range(0, n):
for y in range(0, n):
if(O_graph[x][y] == 'G'): O_graph[x][y] = 'R'
no_cnt = 0
yes_cnt = 0
def DFS(x, y, graph, v):
if x >= n or x <= -1 or y >= n or x <= -1 or graph[x][y] == 0: return False
else:
if(v == graph[x][y]):
graph[x][y] = 0 # visited
DFS(x+1, y, graph, v)
DFS(x-1, y, graph, v)
DFS(x, y+1, graph, v)
DFS(x, y-1, graph, v)
for i in range(0, n):
for j in range(0, n):
# 적록색맹 없음
if X_graph[i][j] != 0:
DFS(i,j,X_graph, X_graph[i][j])
no_cnt += 1
# 적록색맹 있음
if O_graph[i][j] != 0:
DFS(i, j, O_graph, O_graph[i][j])
yes_cnt += 1
print(no_cnt, yes_cnt)근데 이 코드를 pypy3에서 실행하면 메모리 초과가 뜬다
pypy3에서 메모리초과가 뜨길래 혼자 막 '아 이거 깊은복사 사용해서 그런거네' 하면서 visited 방식으로도 문제를 한번 더 풀었다...
근데 방식은 거의 비슷하다
visited = [[0] * n for _ in range(n)]
no_cnt = 0
yes_cnt = 0
def DFS(x, y, v):
if x >= n or x <= -1 or y >= n or x <= -1 or visited[x][y] == 1: return False
else:
if(v == graph[x][y]):
visited[x][y] = 1 # visited
DFS(x+1, y, v)
DFS(x-1, y, v)
DFS(x, y+1, v)
DFS(x, y-1, v)기본 베이스에서 이전값과 비교하기 위한 v 파라미터를 추가해준것 밖에 없다
그래서 방문하지 않은곳이고, 이전 값과 같으면, 방문처리해주고 DFS 해주도록 해줬다
입력받은 graph를 계속 사용하므로 적록색맹이 없는 사람의 DFS가 끝나면
for x in range(0, n):
for y in range(0, n):
if(graph[x][y] == 'G'): graph[x][y] = 'R'
visited = [[0] * n for _ in range(n)]적록생맥이 있는 사람용으로 graph 내용을 바꾸고 방문 배열도 같이 초기화해줬다
그러고 영역 구분을 위해 for문을 돌려주면 끝~
전체 코드 (visited 배열 사용)
import sys
sys.setrecursionlimit(10**6) # 파이썬의 재귀 깊이 지정 (Python3)
input = sys.stdin.readline
n = int(input())
graph = []
for _ in range(n):
graph.append(list(input()))
visited = [[0] * n for _ in range(n)]
no_cnt = 0
yes_cnt = 0
def DFS(x, y, v):
if x >= n or x <= -1 or y >= n or x <= -1 or visited[x][y] == 1: return False
else:
if(v == graph[x][y]):
visited[x][y] = 1 # visited
DFS(x+1, y, v)
DFS(x-1, y, v)
DFS(x, y+1, v)
DFS(x, y-1, v)
for i in range(0, n):
for j in range(0, n):
if visited[i][j] == 0:
DFS(i,j, graph[i][j])
no_cnt += 1
for x in range(0, n):
for y in range(0, n):
if(graph[x][y] == 'G'): graph[x][y] = 'R'
visited = [[0] * n for _ in range(n)]
for i in range(0, n):
for j in range(0, n):
if visited[i][j] == 0:
DFS(i, j, graph[i][j])
yes_cnt += 1
print(no_cnt, yes_cnt)
깊은복사를 먼저 작성하긴 했지만 맞았습니다!를 먼저 받은건 visited 방식이었다...
visited 방식으로 하고 나서 pypy3말고 python3으로 실행해야된다는 것을 깨달아버려서..!!!
그래도 이제 아이디어는 빨리 떠올라서 다행이지만 푸는데 오래걸려서 쪼매 그렇네...ㅠ
