adfsfsf   1년 전

답은 count의 값으로 두겠습니다. 초기값은 0입니다.

처음에는 N개의 행을 받으면서, M개의 칸을 확인합니다. 
    'X'가 있다면, '.'들을 [0,0]으로 바꿔줍니다.
    없다면, '.'들을 [1,0]으로 바꿔줍니다.
다음으로 M개의 열에 대해 'X'의 유무에 따라 처리합니다.
    'X'가 없다면
        해당 열의 list인 값들은 1번 인덱스를 1로 바꿔줍니다.
            [1,1]이 된 경우 2에 대한 리스트, [0,1]이 된 경우 1에 대한 리스트에 좌표를 저장합니다.
    'X'가 있다면
        해당 열의 list인 값들에 대해
            [1,0]인 경우 1에 대한 큐에 좌표를 저장합니다.
그 후, 2에 대한 리스트가 빌 때까지 다음을 반복합니다.
    좌표를 꺼내고, 그 좌표의 값이 [1,1]이라면
        그 위치의 값을 'X'로 바꾸고 count를 증가시킵니다.
        그 위치를 기준으로 가로/세로의 십자 위치의 칸들을 확인하고, list인 값들에 대해, 같은 열의 칸들에 대해서는 뒷 값, 같은 행의 칸들에 대해서는 앞 값을 감소시킵니다. (N+M-1개 칸)
        감소시킨 결과 하나의 값이 1이라면 1에 대한 큐에 해당 값의 좌표를 넣어줍니다.
그 후, 1에 대한 리스트가 빌 때까지 다음을 반복합니다.
    좌표를 꺼냅니다.
        그 좌표가 list이고, 두 값의 합이 1이라면 count를 증가시킵니다.
            만약 [1,0]이라면 같은 행의 다른 칸들에 대해, list라면 앞의 값을 감소시킵니다.
            만약 [0,1]이라면, 같은 열의 다른 칸들에 대해, list라면 뒤의 값을 감소시킵니다.

지도로부터 큐 2개를 얻기까지, 2번 지도를 확인합니다.
처음에는 'X'가 아닌 칸들에 대해 list로 만듭니다.
다음에는 list인 칸들의 값을 갱신 한 후 큐에 해당 칸들의 좌표를 넣어줍니다.
큐 2개를 확인하게 되는 좌표 값의 개수는 합쳐서 최대 N이며, 각 좌표마다 최대 N+M 개의 list에 대해 값을 갱신하고, 큐에 넣습니다.(N>=M인 경우)

결과적으로 시간복잡도는 최대 N^2, 평균 NM이 된다고 볼 수 있겠습니다.

댓글을 작성하려면 로그인해야 합니다.