[백준 3085] 사탕게임

04-20 

 

풀이 

인접한 노드를 구하는 방법을 찾아보다가 

'델타를 이용한 상하좌우 노드 탐색' 을 해보자고 생각했다. 그전에 문제들도 델타를 이용한것처럼 보였는데 이해가 잘 되지않았다. 오늘은 한 티스토리 글을 보고 좀 이해가 가기시작했다. 

코드는 약간 그럴싸 했지만 당연 답지를 볼수밖에 

그래도 델타부분은 비슷했다 ㅎㅎ 

 

코드 

#최대 개수 세기 
def count_candy():
    row_cnt,col_cnt,row_max,col_max =1,1,-1e9,-1e9 

    #행 계산 
    for i in range(n):
        for j in range(n-1): 
            #행 기준 동일한 색상이라면 
            if candy[i][j] == candy[i][j+1]:
                row_cnt+=1 
            else: 
                row_cnt =1
            row_max=max(row_cnt,row_max) 
        row_cnt =1 
    #열 계산 

    for j in range(n): 
        for i in range(n-1): 
            #열 기준 동일한 색상이라면 
            if candy[i][j]==candy[i+1][j]:
                col_cnt +=1 
            else: 
                col_cnt=1
            col_max=max(col_cnt,col_max) 
        col_cnt=1 
        #먹을수 있는 최대 사탕개수 구하기 
    answer = max(row_max,col_max) 
    return answer 
ans=0 
 
n =int(input()) 
candy = [list(input()) for _ in range(n)]
'''
dx=[0,0,-1,1] # 좌우 
dy=[-1,1,0,0] # 상하 
'''
steps =[[-1,0],[1,0],[0,-1],[0,1]] # 상,하,좌,우 
for i in range(n):
    for j in range(n): 
        for k in range(4): 
            nx = i+steps[k][0]
            ny = j+steps[k][1]
            #보드를 벗어나면 건너뛰기 
            if nx<0 or nx>=n or ny<0 or ny>=n:
                continue
            #인접한 두 칸이 다른 색의 사탕이라면 
            if candy[i][j] != candy[nx][ny]: 
                candy[nx][ny], candy[i][j] = candy[i][j],candy[nx][ny]
                #이전의 사탕 개수와 비교하며 최댓값 생성 
                ans = max(ans,count_candy()) 
                #인접한 두 칸 원위치 
                candy[i][j], candy[nx][ny]=candy[nx][ny], candy[i][j] 
                
print(ans)

다른코드들도 좀 찾아봐야겠다.