[www.acmicpc.net/problem/10026]
#풀이-dfs,bfs 알고리즘을 사용하면 된다.
1. 적록색약이 아닌사람이 봤을 때 dfs알고리즘을 실행한다.
2. 적록색약인 사람이 봤을 때 dfs알고리즘을 실행하는데 R과G를 동일한 것으로 취급한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | import sys input = lambda : sys.stdin.readline().rstrip() #비적록색약 일반적인 dfs def dfs_n(i,j): stack=[(i,j)] visit[i][j]=1 color=data[i][j] while stack: x,y=stack.pop() for i in range(4): da=x+dx[i] db=y+dy[i] if 0<=da<N and 0<=db<N and not visit[da][db] and color == data[da][db]: visit[da][db]=1 stack.append((da,db)) #적록색약 dfs R과G를 동일하게 취급 def dfs_rg(i,j): stack=[(i,j)] visit[i][j]=0 color=data[i][j] while stack: x,y=stack.pop() for i in range(4): da=x+dx[i] db=y+dy[i] if 0<=da<N and 0<=db<N and visit[da][db]: if color == data[da][db]: visit[da][db]=0 stack.append((da,db)) elif (color == "G" or color == "R") and (data[da][db] == "G" or data[da][db] == "R"): visit[da][db]=0 stack.append((da,db)) N=int(input()) data=[input() for _ in range(N)] visit=[[0 for _ in range(N)] for _ in range(N)] dx=[1,-1,0,0] dy=[0,0,1,-1] result_n=0 result_rg=0 #visit이 1이면 지나간곳 for i in range(N): for j in range(N): if not visit[i][j]: dfs_n(i,j) result_n+=1 #visit이 0이면 지나간곳 for i in range(N): for j in range(N): if visit[i][j]: dfs_rg(i,j) result_rg+=1 print(result_n,result_rg) | cs |
댓글 쓰기