파이썬으로 이진 행렬에서 특수 위치의 개수 찾기

m x n 크기의 이진 행렬(binary matrix)이 주어졌을 때, 행렬 안에서 특수 위치(special position)의 개수를 구하는 문제입니다. 여기서 특수 위치란 다음 조건을 만족하는 좌표 (i, j)를 의미합니다.

• mat[i][j]의 값이 1이다
• i번째 행과 j번째 열에 있는 나머지 모든 요소가 0이다

예를 들어 아래와 같은 행렬이 입력으로 주어진다고 가정해 보겠습니다.

이 경우 출력은 3이 됩니다. 특수 위치는 (0, 0), (1, 2), (3, 1) 세 곳이기 때문입니다. 각 위치의 값은 1이면서, 해당 행과 열에는 그 값 외에 다른 1이 존재하지 않습니다.

해결 접근 방법

이 문제는 각 행을 순회하며 조건을 검사하는 방식으로 해결할 수 있습니다. 핵심 단계는 다음과 같습니다.

1. 특수 위치의 개수를 저장할 변수 special을 0으로 초기화합니다.
2. 행렬의 각 행 i에 대해 반복합니다.
3. 만약 해당 행에 1이 정확히 하나뿐이라면:
   • 그 1의 열 인덱스(indexOfOne)를 구합니다.
   • 같은 열에 있는 모든 요소를 위에서 아래로 검사하며 1의 개수(numOfOne)를 셉니다.
   • 검사 도중 numOfOne이 1보다 커지면 더 이상 볼 필요가 없으므로 반복문을 종료합니다.
4. 열 검사가 끝난 뒤 numOfOne이 정확히 1이라면, 그 위치는 특수 위치이므로 special을 1 증가시킵니다.
5. 모든 행에 대한 검사가 끝나면 special 값을 반환합니다.

파이썬 구현 예제

위 알고리즘을 파이썬 코드로 구현하면 다음과 같습니다.

def solve(matrix):
    special = 0
    for i in range(len(matrix)):
        if matrix[i].count(1) == 1:
            numOfOne = 0
            indexOfOne = matrix[i].index(1)
            for j in range(len(matrix)):
                if matrix[j][indexOfOne] == 1:
                    numOfOne += 1
                if numOfOne > 1:
                    break

            if numOfOne == 1:
                special += 1

    return special

matrix = [[1,0,0,0,0],
    [0,0,1,0,0],
    [0,0,0,1,1],
    [0,1,0,0,0]]
print(solve(matrix))

입력

[[1,0,0,0,0],
[0,0,1,0,0],
[0,0,0,1,1],
[0,1,0,0,0]]

출력

3

동작 원리 정리

이 알고리즘의 시간 복잡도는 O(m x n)입니다. 각 행에 대해 최악의 경우 전체 열을 한 번씩 검사하기 때문입니다. 행에 1이 하나뿐인 경우에만 열 검사를 진행하므로, 1이 여러 개인 행은 빠르게 건너뛰어 불필요한 연산을 줄일 수 있다는 점이 효율성의 핵심입니다. 또한 열 검사 중 1이 두 개 이상 발견되면 즉시 break로 탈출하여 성능을 더욱 개선합니다.