1.8 0 행렬

문제

MXN행렬의 한원소가 0인경으 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘을 작성하라

 

접근법

행렬을 순회해 나가면서 0인 셀을 발견하면 그 셀이 속한 행과 열을 모두 0으로 바꾸는 방식을 취한다면 0으로 바뀐 행이나 열의 또다른 셀을 나중에 방문하면 그 셀이 속한 행과 열도 모두0으로 바뀌는 문제가 발생한다. 

따라서 0인 셀의 위치를 저장해두고 이후에 탐색 후 해당 행과 열을 변경해주어야 할 것이다. 

 

1. 0의 위치를 기록할 행렬 하나를 더둔다 -> Space Complexity  O( MN) 

 

2. 바뀔 행과 열만 체크한다 -> Space Complexity(M+N) 

 

3. 행렬의 0번째 행과 열에 바뀌어야 하는지의 여부를 체크한다. -> Space Complexity 0(1)

 - 첫번째 행과 첫번째 열안에 0이 있는지 확인한다 ( 나중에 첫번째 행과 열을 0으로 만드는 작업이 필요한지 체크)

 - 나머지 부분을 순회하면서 matrix[i][j] ==0 을 만나면 matrix[0][j] = 0 matrix [i][0] = 0 으로 설정한다. 

 - matrix[i][0]과 matrix[0][j]가 0인 행과 열을 변경시켜준다

 - 맨처음에 0번째 행과 열에 0이 있었다면 0번째 행 또는 열을 0으로 변경시켜준다. 

 

배운점

따로 저장공간을 사용하지 않더라도 기존의 할당된 공간에 체크를 함으로써 같은 기능을 구현할 수 있다는 것이 신기했다.