TIL 2023.04.14

와 이번 알고리즘 문제는 정말 어려웠다

https://school.programmers.co.kr/learn/courses/30/lessons/120866?language=python3 

프로그래머스

def solution(board):
    answer = 0
    n = len(board)
    mine = []

    for x in range(n):
        for y in range(n):
            if board[x][y] == 1:
                mine.append((x, y))

    for x, y in mine:
        validation = [(x - 1, y - 1), (x - 1, y), (x - 1, y + 1), (x, y - 1), (x, y + 1), (x + 1, y - 1), (x + 1, y),
                      (x + 1, y + 1)]
        for i in validation:
            if i[0] < 0 or i[0] >= n or i[1] < 0 or i[1] >= n:
                pass
            elif board[i[0]][i[1]] == 1:
                pass
            else:
                board[i[0]][i[1]] = 2

    for z in board:
        answer += z.count(0)

    return answer

일단 내 풀이는 이렇다.

먼저, n 변수에 board의 길이를 할당하고, mine 리스트를 만들어서 board에서 지뢰가 있는 좌표들을 저장한다.

그리고 나서, mine 리스트에 저장된 모든 지뢰 좌표를 순회하면서, 해당 지뢰 주변 8개 좌표에 대해서 숫자 2를 할당한다. 이때, validation 리스트를 사용하여 지뢰 주변 8개 좌표를 구하고, 해당 좌표가 배열의 인덱스를 벗어나지 않는지 확인합니다. 벗어나지 않는다면 해당 좌표에 있는 값이 1인지 0인지에 따라서 숫자 2를 할당하거나 그대로 두어서 지뢰 주변에 숫자 2가 할당된 배열을 만듭니다.

마지막으로, 변경된 board 배열에서 숫자 0의 개수를 반환한다.

 

한 시간이 넘게 걸린 문제다.

처음에 지뢰의 좌표를 구하는데

    for x, s in enumerate(board):
        for n in s:
            if n == 1:
                y = s.index(n)
                mine.append((x, y))
                s[y] = 0

이렇게 코드를 짰었는데,

s[y] 의 값을 0으로 바꿔준 이유는 s안에 1이 여러개 존재할 경우 첫번째 1의 인덱스값만 가져오는게 문제가 됐었다

그래서 이미 좌표를 구하는게 끝난 지뢰는 0으로 바꿔줘서 다시 인덱스를 구하지 못하게 한 것이다.

이렇게 하니 문제가 board의 지뢰들이 모두 0으로 변해서 사라지는 문제가 생겼다.

추후에 안전지대의 수를 구하는데 원래 지뢰의 위치도 0으로 나오게 돼 문제가 된다.

    board_copy = board.copy()
    for x, s in enumerate(board_copy):
        for n in s:
            if n == 1:
                y = s.index(n)
                mine.append((x, y))
                s[y] = 2

다음에 이렇게 수정했다. 얕은 복사를 해서 원본 board 2차원 배열은 수정이 되지 않게끔 했다.

그런데 그게 생각대로 되지가 않았다.

ChatGPT 선생님께서는

Python에서 리스트를 얕은 복사(shallow copy)하는 경우, 새로운 리스트 객체가 생성되지만 내부의 요소는 원본과 동일한 객체를 참조하게 됩니다. 따라서 원본 리스트와 얕은 복사한 리스트 모두 같은 객체를 참조하게 되므로, 한 쪽에서 리스트의 요소를 변경하면 다른 쪽에서도 동일한 변경사항이 반영됩니다.

라고 하신다. 그래서 완전히 새로운 객체를 만드려면 깊은 복사를 이용해야 하는데, copy 모듈의 deepcopy 함수를 쓰라고 하신다.

 

그래서 위 코드처럼 조건을 완전히 수정해주었다. 훨씬 간결하고 오류도 없다.

 

그 후 지뢰 주변 상하좌우대각선의 좌표를 구할 때 try exept 문으로 board의 인덱스 값이 초과되버리는 경우는 무시해버렸더니

인덱스가 음수일 때는 인덱스를 뒤부터 가져와서 완전히 다른쪽 좌표가 위험지대로 변했다.

그래서 이 부분도 위 처럼 코드를 수정했다.

 

효율적인 코드는 아니다.

다른 사람의 풀이에 훨씬 간결한 코드도 있는데 나는 봐도 뭔지 모르겠다.