SWEA 1258. 행렬찾기 (Python)(D4)

bfs 문제이다.

• 주어진 행렬(li)와 사이즈가 같은 2차원배열 visit을 만들어준다.
• 행렬을 순회하면서 visit[i][j]=0이고(방문하지않은곳), li[i][j]!=0이면 (i,j)을 deque에 넣어주고 size값을 갱신해준다.
  - 대각선으로는 이동하지 않으므로, dx, dy설정에 유의
• 이때, size는 [들린횟수(크기),직사각형의 왼쪽위값(처음 방문할때의 값),직사각형의 오른쪽 아래값(마지막 방문할때의 값)]
• 처음 방문할때의 x,y가 직사각형의 왼쪽 위 값이고, 직사각형의 오른쪽 아래값은 계속 갱신해준다
  - dx, dy설정을 잘하면 q가 다 비었을 때 직전의 x,y값만 넣어줘도 된다.
• q가 비어서 while문을 빠져나오면(직사각형 순회완료), [크기,x길이,y길이]를 결과배열에 추가해준다.
• 최종적으로, 결과배열을 2차원정렬([0] 오름차순 -> [1] 오름차순) 한 뒤, 결과값에 추가!

from collections import deque
dx=[0,0,1,-1] # 상하좌우로 이동하므로 
dy=[1,-1,0,0]
res=[]

for m in range(int(input())):
    tmpli=[]
    tmp=""
    N=int(input())
    li=[[0]*(N+1)]
    visit=[[0]*(N+1) for i in range(N+1)]
    for i in range(N):
        li.append([0]+list(map(int,input().split())))

    for i in range(1,N+1):
        for j in range(1,N+1):
            size=[0,0,0] #초기값 선언
            if li[i][j]!=0 and visit[i][j]==0: #해당구역에 화학물질이 있고 처음방문할 경우
                q=deque()
                q.append((i,j))
                visit[i][j]=1
                size=[size[0]+1,[i,j],[0,0]] #크기갱신, 직사각형의 왼쪽위값 갱신
                while q:
                    x,y=q.popleft()
                    for k in range(4): #상하좌우 방문
                        nx=x+dx[k]
                        ny=y+dy[k]
                        if 1<=nx<=N and 1<=ny<=N:
                            if li[nx][ny]!=0 and visit[nx][ny]==0: #해당구역에 화학물질이 있고 처음방문할 경우
                                visit[nx][ny]=1 #방문처리
                                q.append((nx,ny))
                                size[0]+=1 # 크기갱신
                                size[2]=[nx,ny] if nx>=size[2][0] and ny>=size[2][1] else size[2] #조건부로 직사각형의 오른쪽하단값 갱신(x,y) 둘다 가장 큰값
            if size[0]:
                tmpli.append([size[0],size[2][0]-size[1][0]+1,size[2][1]-size[1][1]+1]) # 해당구역값을 추가해줌([크기,x의길이,y의길이])
    tmpli.sort(key=lambda x:(x[0],x[1])) #2차원정렬, x[0]오름차 -> x[1] 오름차순
    tmp+=str(len(tmpli))+" "
    for i in tmpli:
        tmp+=str(i[1])+" "+(str(i[2])+" " if i[1]!=i[2] else "")
    res.append(tmp)
for i in range(len(res)):
    print("#%d %s"%(i+1,res[i]))