0227_ 오늘도 고생했다 .. SW 1258번 : 행렬찾기

오늘 문제 출처 : 삼성 소프트웨어 엑스퍼트 아카데미, 1258번 행렬찾기 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18LoAqItcCFAZN

SW Expert Academy

 

여러번 시도했던 문제.

bfs로도 풀 수 있다고 들었는데 나는 bfs, dfs 개념을 잘 모르고 아직 쓰는 것도 서툴다.. (이것도 또 공부해야 해)

 

이 문제 첨에 접근할 때 행렬 처음 위치에서 값이 있으면 열을 증가시키고 0을 만나면 행을 증가시키며 이동하고,, 결론은 처음 찍었던 좌표 위치와 마지막 이동한 좌표 위치를 비교해서 거리를 구하려고 했는데,, 좋은 시도가 아니었다. 2시간 동안 끙끙대다가 결국 한 마음씨 고운 천사의 도움을 받아 코드 방향을 재설정하고 풀었다.

 

[접근 순서]

1. 0보다 큰 위치에서 좌표 찍고, 델타 값을 이용해 행렬에서 이동하였다.

2. 최대 행과 열의 크기를 max값으로 구해주었고,

3. 구한 행과 열의 max값들과 크기 r*c를 리스트 형태로 저장해두었고

4. sort()를 이용해 정렬하여 값을 구할 수 있었다.

 

특히 4번이 ouput을 구하기 위해 필수적인 구간인데, 이 부분 코드를 작성하면서 우여곡절이 많았다.

정렬할 때 단순히 오름차순 정렬이 아니었기에 각 행렬의 크기, 행의 크기를 순서대로 고려해서 정렬해야 했다.

처음에는 r*c 행렬 크기는 고려하지 않고 정렬하기도 했고, 튜플형태로 (r,c)를 묶어서 리스트에 넣고 정렬하기도 했는데 원하는 값이 잘 안나왔다.. 그래서 아래 출력부분은 함께 공부하는 스터디원 분의 코드에서 도움을 받아 완성할 수 있었다.   

 

sort로 정렬시 하나의 값이 아니라 여러 값들이 튜플이나 리스트 형태로 들어왔을 때, 정렬 순서는 1-2-3 ... 순으로 우선 순위가 앞에서부터 차례대로 정해진다. 추가로 항상 헷갈리는 sort 정리는 아래에.

 

▷sort 메소드와 sorted() 함수 차이 정리
둘 다 똑같이 오름차순 정렬을 하지만, 차이점은 

sort 메소드 : 원본 리스트의 값을 변경해버리며, 새로운 변수에 값을 할당하지 않는 이상 None 리턴
                 print(sort(원본 리스트)) => None 
sorted() 함수 : 원본 리스트에 영향 주지 X, 새로운 리스트를 만들어 리턴
                 print(sorted(원본 리스트)) => 오름차순 리스트 반환

 

#상하좌우
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for t in range(1, int(input())+1):
    res = []
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if arr[i][j] > 0:
                #시작점
                x = i
                y = j
                #최대 행열의 크기
                max_r = 0
                max_c = 0
                #열 크기
                while 0 <= y <n and arr[x][y] != 0:
                    y = y + dy[3]
                max_c = y - 1
 
                #행 크기
                while 0 <= x < n and arr[x][y-1] != 0:
                    x = x + dx[1]
                max_r = x-1
 
                for k in range(i, max_r+1):
                    for m in range(j, max_c+1):
                        arr[k][m] = 0
                res.append((max_r-i+1, max_c-j+1))
    matrix = []
    for r, c in res:
        matrix.append([r*c,r,c])
    matrix.sort()
 
    print(f'#{t} {len(matrix)}', end=' ')
    for i in range(len(matrix)):
        print(matrix[i][1], matrix[i][2],end=' ')
    print()

 

P.S. 내일부터는 312 공부법 꼭 실천하자