[Python/파이썬] 백준 9555번 대회 장소 준비

https://www.acmicpc.net/problem/9555

코드

import sys
input = sys.stdin.readline

dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

for _ in range(int(input())):
    n, m = map(int, input().split())
    teams = [list(map(int, input().split())) for _ in range(n)]

    answer = set()
    for x in range(n):
        for y in range(m):
            if teams[x][y] == -1 or teams[x][y] in answer:
                continue
            for d in range(8):
                nx = x+dx[d]
                ny = y+dy[d]
                if 0 <= nx < n and 0 <= ny < m and teams[nx][ny] == teams[x][y]:
                    answer.add(teams[x][y])
                    break
    print(len(answer))

 

시간복잡도만 보면 O(N^3)으로 크긴 한데, 문제에서 주어진 조건의 범위가 크지 않고(1 ≤ T ≤ 100, 1 ≤ N, M ≤ 100), 집합을 사용하여 이미 집계된 학교에 대해서는 연산을 다시 하지 않도록 처리했기 때문에 시간 내로 충분히 통과할 수 있다.