Baek_10026

오늘 아침에 골드5를 풀어버리고 어제 당한 DFS의설욕을 풀고자 선택했다...
문제는 읽기도 간단 고민도 할거 없드랑
대충 dfs 2번 돌릴껀데 처음에는 기본 두번재는 R,G를 서로 dfs 통과하도록 해주면 된다.
어제 배운 False로 채운 이중리스트를 visit으로 활용해 시간단축을 해보겠다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(15000)
cnt = int(input())
matrix = [list(input().rstrip()) for _ in range(cnt)]

visit1 = [[False]*cnt for _ in range(cnt)]
visit2 = [[False]*cnt for _ in range(cnt)]
def dfs1(x,y,alpha):
    for a,b in [[0,1],[1,0],[0,-1],[-1,0]]:
        xa,yb = x+a,y+b
        if 0<=xa<cnt and 0<=yb<cnt and matrix[xa][yb] == alpha and not visit1[xa][yb]:
            visit1[xa][yb] = True
            dfs1(xa,yb,alpha)

def dfs2(x,y,alpha):
    for a,b in [[0,1],[1,0],[0,-1],[-1,0]]:
        xa,yb = x+a,y+b
        if alpha == 'R' or alpha == 'G':
            if 0<=xa<cnt and 0<=yb<cnt and (matrix[xa][yb] == 'R' or matrix[xa][yb] == 'G') and not visit2[xa][yb]:
                visit2[xa][yb] = True
                dfs2(xa,yb,alpha)
        else:
            if 0<=xa<cnt and 0<=yb<cnt and matrix[xa][yb] == alpha and not visit2[xa][yb]:
                visit2[xa][yb] = True
                dfs2(xa,yb,alpha)
ans1,ans2 = 0,0
for i in range(cnt):
    for j in range(cnt):
        if not visit1[i][j]:
            visit1[i][j] = True
            dfs1(i,j,matrix[i][j])
            ans1+=1
        if not visit2[i][j]:
            visit2[i][j] = True
            dfs2(i,j,matrix[i][j])
            ans2+=1
print(ans1,ans2)

오늘의 뻘짓은 일단 visit 저 형태를 첨 만들어봐서

visit = [[False]*n]*n

이렇게 만들었는데결론은 틀렸더라.
한 줄이 바뀌어버려서 깜짝 놀랐네....
일단 그래도 다시 보고 해결했고 또 제귀 제한 빼먹어서 런타임에러 걸렸다ㅠ 내 정확도ㅠㅠㅠ
화나서 15000으로 바꿔버리고 돌려버렸는데 통과~~~
dfs 이정도면 잘하는거 인정?