[항해99] WIL(2) - 알고리즘 공부

이번 주에 한 일

본격적인 기술공부 하기 전에, 알고리즘 공부를 했다.

스택, 큐, 힙, 그래프, DFS를 공부하면서 기업 코딩테스트 준비를 했다. 

 

이번 주에 제일 기억에 남았던 문제

DFS 에서 단지번호 붙이기 문제가 제일 기억에 많이 남았는데, 

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

2667번: 단지번호붙이기

강의에서 알려준 DFS 스택 스켈레톤 코드에서 변수만 넣으면 작동하겠지 라는 생각으로 다가가서 문제를 풀었으나, 스켈레톤 코드에서 문제가 있었다.

문제 코드 

n = int(input())
 
# 일단 adjMatrix를 만들고 시작하자.
mat = [[-1 for i in range(n)] for j in range(n)]
for i in range(n):
    s = input()
    for j in range(n):
        mat[j][i] = int(s[j])
 
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
 
rows, cols = len(mat), len(mat[0])
 
cnt = 0
ans = []
for row in range(rows):
    for col in range(cols):
        # 섬이 아닌 경우 건너 뜀.
        if mat[row][col] != 1:
            continue
 
        stack = [(row, col)]
        cnt += 1
        apart = 0
        while stack:
            print("----------------")
            print("stack : ", stack)
            x, y = stack.pop()
            mat[x][y] = 0
            print("x, y : ", x, y)
            print("apart : ", apart)
            print("----------------")
 
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or nx >= rows or ny < 0 or ny >= cols or mat[nx][ny] != 1: # 문제코드
                    continue
                stack.append((nx, ny))
                apart += 1
        ans.append(apart)
 
print(cnt)
ans.sort()
for i in ans:
    print(i)

38번째 줄을 보면 서로 붙어있는 지를 체크하는 mat[nx][ny] != 1 이 있는데 이 조건이 아니라면 스택에 nx ny 즉 인근 좌표를 넣는데, 정작 그래프의 값을 조정하는건 윗쪽의 while 문에서 이루어지기 때문에 중복된 값이 들어가서 생기는 문제였다.

 

왜 그런지 몰라서 출력문을 찍어보고 디버깅을 해보니 위와같은 상황이 있다는 것을 알게되었고 문제 해결 방향에 맞게 코드를 수정해서 해결했다.

수정 코드 

n = int(input())
 
# 일단 adjMatrix를 만들고 시작하자.
mat = [[-1 for i in range(n)] for j in range(n)]
for i in range(n):
    s = input()
    for j in range(n):
        mat[j][i] = int(s[j])
 
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
 
rows, cols = len(mat), len(mat[0])
 
cnt = 0
ans = []
for row in range(rows):
    for col in range(cols):
        # 섬이 아닌 경우 건너 뜀.
        if mat[row][col] != 1:
            continue
 
        stack = [(row, col)]
        cnt += 1
        apart = 0
        while stack:
            x, y = stack.pop()
            if mat[x][y] != 1:
                continue
            apart += 1
            mat[x][y] = 0
 
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or nx >= rows or ny < 0 or ny >= cols:
                    continue
                stack.append((nx, ny))
        ans.append(apart)
 
print(cnt)
ans.sort()
for i in ans:
    print(i)

 

느낀 점 

생각했던 값과 다른 값이 나오거나 틀린 답이 나올 경우 출력해보고 디버깅해보면서 문제를 해결해보자.