𝐓𝐨𝐝𝐚𝐲 𝐈 𝐋𝐞𝐚𝐫𝐧 2022.04.06.수

0406 Today I Learn

오늘은 사실 Django를 배웠는데 배운게 너무 많아서 정리하기가 애매해 일단 문제풀이에 대한 TIL을 올리기로 했다. 내일 다시 실습하면서 Django는 어려웠던 부분에 대해 따로 정리해서 올려야겠다.

---

오늘은 A형 대비를 위한 특강을 위해 SWEA문제 1개를 풀었다.BFS를 이용한 문제인데, 사실 더 짧은 코드로 최적화 가능해 보인다.

문제 링크

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AX_Pn1I6fBQDFARi

나의 풀이

from collections import deque
T = int(input())
for tc in range(1,T+1):
    N,M = map(int,input().split())
    arr=[list(input()) for _ in range(N)]
    a_visit = [[0]*M for _ in range(N)]
    b_visit = [[0]*M for _ in range(N)]
    a_cnt,b_cnt=0,0
    a_max,b_max=0,0
    
    def a_bfs(y,x):
        global a_max
        q = deque()
        q.append((y,x))
        cnt=1
        while q:
            ny,nx = q.popleft()
            directy=[-1,1,0,0]
            directx=[0,0,-1,1]

            for i in range(4):
                dy=directy[i]+ny
                dx=directx[i]+nx

                if 0<=dy<N and 0<=dx<M:
                    if arr[dy][dx]!='A': continue
                    if a_visit[dy][dx]!=0:continue
                    a_visit[dy][dx]=1
                    cnt+=1
                    q.append((dy,dx))
        if a_max<cnt:
            a_max=cnt

    def b_bfs(y,x):
        global b_max
        q = deque()
        q.append((y,x))

        cnt=1
        while q:
            ny,nx = q.popleft()
            directy=[-1,1,0,0]
            directx=[0,0,-1,1]

            for i in range(4):
                dy=directy[i]+ny
                dx=directx[i]+nx

                if 0<=dy<N and 0<=dx<M:
                    if arr[dy][dx]!='B': continue
                    if b_visit[dy][dx]!=0:continue
                    b_visit[dy][dx]=1
                    cnt+=1
                    q.append((dy,dx))
        if b_max<cnt:
            b_max=cnt

    for i in range(N):
        for j in range(M):
            if arr[i][j] == 'A' and a_visit[i][j] == 0:
                a_cnt+=1
                a_visit[i][j]=1
                a_bfs(i,j)
            if arr[i][j] == 'B' and b_visit[i][j]==0:
                b_cnt+=1
                b_visit[i][j]=1
                b_bfs(i,j)

    answer=max(a_max,b_max)
    print(f'#{tc} {a_cnt} {b_cnt} {answer}')

전략

'A'를 발견했을 때 방문하지 않은 곳이라면 BFS를 돌려주는 것이다.

이 때 a_cnt+1은 개체의 수를 의미한다.

BFS를 타면서 cnt해주는 것은 개체의 크기를 세는 것으로 max값을 갱신해 최대 크기를 구해주었다.

'B'를 발견했을 때도 같은 방법으로 값을 구해준다.

출력에서는 a의 개체수와 b의 개체수 그리고 가장 큰 개체의 크기를 출력해야하는데, max함수를 이용해 a의 최대 크기와 b의 최대 크기를 비교해 answer로 출력해 주었다.