우주의 IT 소행성

나의 코드

import sys
from collections import deque
input = sys.stdin.readline

n, l, r = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(a, b):
    queue = deque()
    queue.append((a, b))
    tmp = []
    tmp.append((a, b))

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                if l <= abs(graph[nx][ny] - graph[x][y]) <= r:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
                    tmp.append((nx, ny))
    return tmp

result = 0
while True:
    visited =[[False] * (n + 1) for _ in range(n + 1)]
    flag = 0
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                visited[i][j] = True
                cur = bfs(i, j)

                if len(cur) > 1:
                    flag = 1
                    people = sum(graph[x][y] for x, y in cur) // len(cur)
                    for x, y in cur:
                        graph[x][y] = people
    if flag == 0:
        break
    result += 1
print(result)

풀이 방법

bfs 후 해당 지역 값 리스트를 저장하여 평균을 냄

평균을 내다가 더이상 상태가 변하지 않는다면 종료

나의 코드

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
maps = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for i in range(n):
    maps.append(list(input()))
    for j in range(m):
        if maps[i][j] == 'R':
            rx, ry = i, j
        elif maps[i][j] == 'B':
            bx, by = i, j


def bfs(rx, ry, bx, by):
    count = 0
    queue = deque()
    queue.append((rx, ry, bx, by))
    visited = [(rx, ry, bx, by)]

    while queue:
        for _ in range(len(queue)):
            rx, ry, bx, by = queue.popleft()
            if count > 10:
                return -1

            if maps[rx][ry] == 'O':
                return count

            for i in range(4):
                nrx, nry = rx, ry
                while True:
                    nrx += dx[i]
                    nry += dy[i]
                    if maps[nrx][nry] == '#':
                        nrx -= dx[i]
                        nry -= dy[i]
                        break
                    elif maps[nrx][nry] == 'O':
                        break

                nbx, nby = bx, by
                while True:
                    nbx += dx[i]
                    nby += dy[i]
                    if maps[nbx][nby] == '#':
                        nbx -= dx[i]
                        nby -= dy[i]
                        break
                    elif maps[nbx][nby] == 'O':
                        break

                if maps[nbx][nby] == 'O':
                    continue

                if nrx == nbx and nry == nby:
                    if abs(nrx - rx) + abs(nry - ry) > abs(nbx - bx) + abs(nby - by):
                        nrx -= dx[i]
                        nry -= dy[i]
                    else:
                        nbx -= dx[i]
                        nby -= dy[i]

                if (nrx, nry, nbx, nby) not in visited:
                    queue.append((nrx, nry, nbx, nby))
                    visited.append((nrx, nry, nbx, nby))
        count += 1
    return -1

print(bfs(rx, ry, bx, by))

풀이 방법

1. 파란 구슬과 빨간 구슬을 각각 움직여야 함

2. 움직이면서 벽이나 구멍을 만나면 아웃

3. 파란 구슬만 구멍에 들어갔거나, 빨간 구슬과 함께 들어갔다면 아웃

나의 코드

import sys
from collections import deque
input = sys.stdin.readline
n, m, k = map(int, input().split())

maps = [[False] * m for _ in range(n)]
visited = [[0] * m for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
count = 1

for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())
    a1, b1, a2, b2 = (n - y1), x1, (n - y2), x2

    for i in range(min(a1, a2), max(a1, a2)):
        for j in range(min(b1, b2), max(b1, b2)):
            maps[i][j] = True


def bfs(a, b):
    global count
    queue = deque()
    queue.append((a, b))
    visited[a][b] = count

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and not maps[nx][ny]:
                if visited[nx][ny] == 0:
                    visited[nx][ny] = count
                    queue.append((nx, ny))


for i in range(n):
    for j in range(m):
        if visited[i][j] == 0 and not maps[i][j]:
            bfs(i, j)
            count += 1

result = []
for i in range(1, count):
    tmp = 0
    for visit in visited:
        tmp += visit.count(i)
    result.append(tmp)

print(count - 1)
print(*sorted(result))

풀이 방법

우리가 사용하는 2차원 배열과, 주어진 직사각형의 (x1, y1) 좌표 (x2, y2)좌표의 좌표계 관점이 다르다.

따라서 a1, b1, a2, b2 = n - y1, x1, n - y2, x2 로 변환하여야 한다.

변환된 좌표계에 bfs를 통해 구역을 분리해준 뒤, 구역 번호에 맞게 숫자를 카운트하여 값을 내주면 되는 간단한 문제

나의 코드

import copy
import sys
from collections import deque
input = sys.stdin.readline
from copy import deepcopy


def go(x, y):
    count = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 0:
            count += 1
    tmp[x][y] = max(0, tmp[x][y] - count)


def bfs(x, y):
    queue = deque()
    queue.append((x, y))

    while queue:
        a, b = queue.popleft()
        visited[a][b] = True

        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] != 0 and not visited[nx][ny]:
                visited[nx][ny] = True
                queue.append((nx, ny))


result = 0
n, m = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

# 시작할 때 부터 전부 녹아있는 경우
# 시작할 때 한번 녹으니까 다 사라진 경우

if sum([sum(i) for i in maps]) in [0, 1]:
    print("0")
    exit()

visited = [[False] * m for _ in range(n)]

# 녹이기
tmp = copy.deepcopy(maps)
for i in range(n):
    for j in range(m):
        if maps[i][j] != 0:
            go(i, j)
maps = copy.deepcopy(tmp)

sum_maps = sum([sum(i) for i in maps])
if sum_maps == 0 or sum_maps == 1:
    print(result)
    exit()

    # 덩어리 찾기
cur = 0
for i in range(n):
    for j in range(m):
        if maps[i][j] != 0 and not visited[i][j]:
            cur += 1
            bfs(i, j)
            if cur > 1:
                print(result)
                exit()

result += 1

while True:
    visited = [[False] * m for _ in range(n)]
    result += 1
    # 녹이기
    tmp = copy.deepcopy(maps)
    for i in range(n):
        for j in range(m):
            if maps[i][j] != 0:
                go(i, j)
    maps = copy.deepcopy(tmp)

    sum_maps = sum([sum(i) for i in maps])
    if sum_maps == 0 or sum_maps == 1:
        print(0)
        break


    # 덩어리 찾기
    cur = 0
    for i in range(n):
        for j in range(m):
            if maps[i][j] != 0 and not visited[i][j]:
                cur += 1
                bfs(i, j)
                if cur > 1:
                    print(result)
                    exit()

풀이 방법

1. go 함수 : map을 돌며 상하좌우 0 개수만큼 현재 칸을 빼줌

2. bfs 함수 : map을 돌며 분리된 빙산이 있는지 확인 (visited)

주의해야 할 점

1. 시작할 때 부터 전부 녹아있는 경우

2. 시작할 때 한번 녹으면 다 사라지는 경우

3. 모두 녹을 때 까지 분리되지 않는 경우

반례

5 5
0 0 0 0 0
0 0 10 10 0
0 10 0 10 0
0 0 10 10 0
0 0 0 0 0

정답 : 0
출력 : 1

4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0