코딩: 말하기 듣기 쓰기-4

이 백준 문제를 통해서 DFS 재귀에 눈을 떴다. 뭐랄까. 코드를 보는법을 다시배우고, 진행상황에 대해 이해하고, 어떻게 생각하면서 무지성하게 바로바로 코딩을 짜지 않는법에 대해서 배운 느낌? 당연히 팀원들의 도움이 있었다. 우선, 이 코드는, 알고리즘을 1년넘게 공부하신, 엄청난 실력자분에게 한번 듣고, 그리고나서 혼자힘으로 시간가는줄모르고 푼 문제이다. 풀고 또 풀고 생각하고 풀고를 계속 반복했다. 물론, 아직까지 여러문제를 접해야 익숙해지지만, 나에게 알고리즘공부 2주만에 좀 뭔가 코드의 이해와 흐름에 도움이 된 문제같다.

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

import sys
sys.setrecursionlimit(10 ** 6)

input = sys.stdin.readline

input_smth = int(input())

matrix = []

for _ in range(input_smth):
    row = list(input().strip())
    matrix.append(row)
#print(matrix)
#-------------------------------------------------
#여기라인까지 백준 문제풀때, 여러개 값을 입력받아야 할때, 써야하는 것들. 외우면 좋다, 아니 외우자
visited = [[False for _ in range(input_smth)] for _ in range(input_smth)]
#false 로 채워놓는다. 방문을 안했다는 뜻이다. 방문을 했을경우에는 True로 바꿀 생각을한다.
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
#좌, 우, 위, 아래를 조사해서, 좌표로 생각해서, 색깔 같으면 dfs재귀 돌린다.
#dfs 재귀로 풀 생각을 하면서 연습해봅시다.

def dfs(x, y):#지금 시작하는 좌표를 재귀할겁니다. 이걸로 매트릭스를 훑을겁니다.
    visited[x][y] = True #방문을 했으니까 True로 바꿔줍니다~
    for search in range(4): # 좌, 우, 위, 아래 검사를 시작~
        nx = x + dx[search] #방문한 좌표 x 한칸 옆에로 이동해서 검사 실시 준비.
        ny = y + dy[search] #방문한 좌표 y 한칸 옆에로 이동해서 검사 실시 준비.
        if nx >= 0 and nx < input_smth and ny >= 0 and ny < input_smth: #양옆 위아래 검사하는데 입력받은 행렬위 밖으로 나가지 않을경우에~
            if visited[nx][ny] == False and matrix[nx][ny] == matrix[x][y]: #만약에 현재좌표 색깔이랑 검사한 색깔이랑 맞으면 dfs에 넣어준다.
                dfs(nx, ny) #이게 무슨말이냐면, 검사하고 색깔 같으면, 옆으로 한칸 이동하면서, 새좌표로 다시 검사 시작.
#-------------------------------------------------
#게임기 같은 느낌으로 생각해주고 편하게 익숙하게 생각하자.

#일반모드
count1 = 0 #일반모드일경우의 영역 세주기
for i in range(input_smth):
    for j in range(input_smth):
        if visited[i][j] == False:
            dfs(i, j)
            count1 += 1

#적록색약이 있으면 R을 G로 바꿔준다. 그상태에서 카운트를 세서 영역 카운트.
for i in range(input_smth): #우선 좌표를 적록색모드로 다 바꿔준다.
    for j in range(input_smth):
        if matrix[i][j] == 'R': #빨간색이면 초록색으로 바꾸기
            matrix[i][j] = 'G'

visited = [[False for _ in range(input_smth)] for _ in range(input_smth)]
#방문하지 않은상태로 초기화를 해줘야한다. 그렇지않으면 일반모드 + 색약모드를 진행하기때문이다. 다시 모든것이 아무것도 방문안된상태로 해주고 시작한다.
count2 = 0 #적록색약모드일경우의 영역세주기
for i in range(input_smth):
    for j in range(input_smth):
        if visited[i][j] == False:
            dfs(i, j)
            count2 += 1

#-------------------------------------------------
#일반모드와 적색약모드 두개가 있다고 생각하자.

print(count1, count2) #마지막으로 일반모드 적색약모드 영역 몇개인지 카운트 출력! 한번 출력해볼까!

한줄한줄 주석을 써가면서 풀어본 결과이다. 우선 이러한 유형의 문제는 크게 두가지로 나뉜다고 생각을 했다. 게임모드와 모드설정.
게임모드는 좌표를 이동하면서 어떻게 찾아낼것인지를 조정하는 부분이다. 이 부분에서 게임판 위를 나가지않게 하는 조건도 필요하고, 한칸씩 위, 아래, 오른쪽, 왼쪽 검사하는 기능도 달아줘야한다. 하지만, 이 게임모드를 어떤 모드로 해줘야 할지를 설정해야하는 조건을 만들어줘야한다. 이 문제에서는, 일반인모드와 적록색약 모드. 이렇게 두개이다. 각각 풀때, 모드가 다르기때문에 겹치지않게 매트릭스를 초기화 해줘야한다.
이문제를 구조화해보면:
인풋섹션:
게임모드:
모드설정:
아웃풋섹션:
이렇게 만들어야한다. 물론 모든문제가 이렇게 돌아가진 않지만, 이걸 생각하면서 하면 큰 도움이 될것이라는 생각을했다.
사실, 예전에 파이썬 패키지로만 사용해본 경험을 갖고 알고리즘 공부를 하면서 파이썬을 다시 정립하고있기때문에 많은 문제가 있는것같다. 특히 해설을 보고도 이해가지 않는경우 대부분은, 내가 문법적으로나 흐름적으로 이해를 완벽히 못해서 그랬던 것이 많았던것같다. 하지만, 이문제를 계기로 어떻게 생각을 구조화하고, 문제를 접근해야 하는지 좀 느낌이 오는것같다. 무지성으로 코드를 쓰기보다 틀리더라도 어떻게 접근하고 이러한 코드를 쓴 근거에 대해서 조목조목 풀어본다면, 알고리즘 공부에 큰 도움이 될것같다. 아주 좋은문제였고 도와준 우리 팀원들에게 고맙다는 말을 꼭 해주고싶다. 나 성장시키랴 각자 공부하랴. 참 고맙다. 우리팀 땡큐!