구현

실버4. 백준 1244 스위치 켜고 끄기

풀이

문제에 나온대로 구현해주면 된다.
인덱스를 문제와 통일시켜주기 위해 0번째 인덱스는 -1 값으로 초기화했고, 접근하지 않도록 구현했다.

남자의 경우, 입력받은 인덱스의 배수번째만 바꿔주면 된다.
여자의 경우, 입력받은 인덱스 기준으로 양쪽 대칭이 값이 같으면 바꿔주면 된다. 어디까지 같은 값을 같는지 체크하고 그 범위만큼 값을 바꿔주는 식으로 했다.

20번째 요소마다 줄바꿈을 해주고 값을 출력해줘야 하는 것에 유의!

코드

from sys import stdin

input = stdin.readline

N = int(input())
switches = [-1]
switches += list(map(int, input().split(" ")))

students = int(input())


def male(idx):
    for i in range(idx, N + 1, idx):
        if switches[i] == 0:
            switches[i] = 1
        else:
            switches[i] = 0


def female(idx):
    before = idx - 1
    after = idx + 1
    is_symmetry_exist = False
    while True:
        if 1 <= before < idx and idx < after <= N:
            if switches[before] == switches[after]:
                is_symmetry_exist = True
                before -= 1
                after += 1
            else:
                before += 1
                after -= 1
                break
        else:
            before += 1
            after -= 1
            break

    if not is_symmetry_exist:
        if switches[idx] == 0:
            switches[idx] = 1
        else:
            switches[idx] = 0
    else:
        for i in range(before, after + 1):
            if switches[i] == 0:
                switches[i] = 1
            else:
                switches[i] = 0


for _ in range(students):
    gender, idx = map(int, input().split(" "))
    if gender == 1:
        male(idx)
    else:
        female(idx)


for i in range(1, N + 1):
    if i % 20 == 1 and i != 1:
        print()
    print(switches[i], end=" ")

실버3. 백준 1913 달팽이

풀이

문제에 나온대로 배열을 가운데서부터 빙글빙글 돌아가면 되는 문제다.
규칙을 찾아보니 다음과 같았다.

첫번째 빙글 : up right down*2 left*2 up*2
두번째 빙글 : up right*3 down*4 left*4 up*4
세번째 빙글 : up right*5 down*6 left*6 up*6
...
i번째 빙글 : up right*(1+i*2) down*(2+i*2) left*(2+i*2) up*(2+i*2)

위에서 찾은 규칙대로 몇번 빙글 돌아야하는지 구해서 계산해주면 된다.

코드

from sys import stdin

input = stdin.readline

N = int(input())

target = int(input())
graph = [[0 for _ in range(N)] for _ in range(N)]
start = N // 2
count = N // 2

x = start
y = start
num = 1


def up(count):
    global num, x, y
    for _ in range(count):
        x -= 1
        num += 1
        graph[x][y] = num


def right(count):
    global num, x, y
    for _ in range(count):
        y += 1
        num += 1
        graph[x][y] = num


def down(count):
    global num, x, y
    for _ in range(count):
        x += 1
        num += 1
        graph[x][y] = num


def left(count):
    global num, x, y
    for _ in range(count):
        y -= 1
        num += 1
        graph[x][y] = num


for i in range(count):
    graph[x][y] = num

    up(1)
    right(1 + (i * 2))
    down(1 + (i * 2) + 1)
    left(1 + (i * 2) + 1)
    up(1 + (i * 2) + 1)


target_r, target_c = 0, 0
for i in range(N):
    for j in range(N):
        if graph[i][j] == target:
            target_r = i + 1
            target_c = j + 1
        print(graph[i][j], end=" ")
    print()

print(target_r, target_c)

골드3. 백준 16236 아기 상어

풀이

문제에 나온대로 구현해주면 되는 문제다.
잘 구현해놓고!!! 문제를 잘못 읽은 부분이 있어서 엄청나게 헤맸다.

헤맨 포인트
1. 물고기의 크기 == 상어의 크기 -> 못 먹음!!! (지나가기만 함)
2. 물고기가 남아있어도 상어의 크기가 작아 다 못먹고 종료해야 하는 경우가 존재

위 2개를 놓쳐서 아주 2시간동안 뱅뱅 돌았다. 테스트케이스를 보고 왜 다르게 나오는지 깨닫느라 한참 걸렸다. 맞게 푼 것 같은데 안 풀릴때는 문제를 처음부터 다시 차근차근 읽어봐야겠다.

코드

from sys import stdin
from collections import deque

input = stdin.readline
N = int(input())

# 물고기의 수
fish = 0

# 상어 좌표
sharkX, sharkY = 0, 0

# 상어 크기
shark_size = 2

# 상어가 먹은 물고기의 수
eat = 0

# 그래프 입력받기
graph = []
for i in range(N):
    data = list(map(int, input().split(" ")))
    for j in range(N):
        if data[j] != 0 and data[j] != 9:
            fish += 1
        elif data[j] == 9:
            sharkX, sharkY = i, j
    graph.append(data)

# 상 하 좌 우
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]


def bfs(sr, sc, cnt, visit):
    q = deque([(sr, sc)])
    visit[sr][sc] = cnt
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                if graph[nr][nc] <= shark_size and visit[nr][nc] == 0:
                    visit[nr][nc] = visit[r][c] + 1
                    q.append((nr, nc))


def check(visit):
    fish_pos_dist = []
    for i in range(N):
        for j in range(N):
            if visit[i][j] != 0 and 1 <= graph[i][j] < shark_size:
                fish_pos_dist.append((visit[i][j], i, j))
    return fish_pos_dist


graph[sharkX][sharkY] = 0
answer = 0
while fish > 0:
    visit = [[0 for _ in range(N)] for _ in range(N)]
    bfs(sharkX, sharkY, answer, visit)
    fish_pos_dist = check(visit)

    # 물고기의 수가 남아있어도 먹을 수 있는 물고기가 없을 수 있음
    if len(fish_pos_dist) == 0:
        break
    fish_pos_dist.sort(key=lambda x: (x[0], x[1], x[2]))

    dist, x, y = fish_pos_dist[0]
    # 물고기 먹기
    eat += 1
    fish -= 1
    graph[x][y] = 0
    if shark_size == eat:
        shark_size += 1
        eat = 0
    sharkX, sharkY = x, y
    answer = dist

print(answer)

그래프

실버1. 백준 2468 안전 영역

풀이

문제에서 힌트를 다 준 상냥한 문제다.

비가 올 수 있는 경우가 최대 100이므로 모든 경우에 대해서 안전영역을 체크해주면 된다.
안전영역은 해당 좌표 값이 비 높이h보다 큰 경우 해당되며, 상하좌우로 인접한 영역만 동일한 영역으로 고려한다. 따라서 인접한 영역을 전부 훑어야하므로 BFS방식을 사용했다.

모든 높이에 대해서 훑어봐야 하므로 입력받은 배열을 deepcopy메서드를 사용해서 복사한 뒤 사용했다.

방문여부는 따로 배열을 만들어서 관리하지 않고, 높이가 될 수 없는 값인 0으로 바꿔서 처리해줬다.

주의할 점은 문제에도 나와있지만, 모든 영역이 비에 잠기지 않을 수 있다는 것이다. 즉, 안전영역의 최솟값은 1이다.

위의 설명 그대로 구현하면 된다.

코드

from sys import stdin
from collections import deque
from copy import deepcopy

input = stdin.readline

N = int(input())

max_height = 0
graph = []
for _ in range(N):
    data = list(map(int, input().split(" ")))
    max_height = max(max_height, max(data))
    graph.append(data)

# 상 하 좌 우
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]


def bfs(i, j, graph, h):
    q = deque([(i, j)])
    # 방문처리
    graph[i][j] = 0
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                # 물에 잠기지 않은 영역일때
                if graph[nr][nc] > h:
                    graph[nr][nc] = 0
                    q.append((nr, nc))


# 아무 지역도 안 잠기는 경우, 안전영역은 전체(1)
safe_area = 1
for h in range(1, 101):
    copy_graph = deepcopy(graph)
    count = 0
    for i in range(N):
        for j in range(N):
            # 물에 잠기지 않은 영역일때
            if copy_graph[i][j] > h:
                bfs(i, j, copy_graph, h)
                count += 1
    safe_area = max(count, safe_area)

print(safe_area)

실버1. 백준 2583 영역 구하기

풀이

괜히 x,y 섞어쓰지말자... 항상 그래프 문제를 풀때는 row, col 개념으로 접근해야 안 헷갈리는 것 같다. (적어도 나는)

입력으로 주어지는 값들은 다음과 같다.

M = 최대 row
N = 최대 col
K = 색칠할 사각형의 범위

사각형은 왼쪽 아래 좌표(LeftRow, LeftCol) 오른쪽 위 (RightRow, RightCol) 값이 주어지는데 색칠되는 범위를 고려하면 LeftRow ~ RightRow-1, LeftCol ~ RightCol-1 범위다. 색칠해야 되는 영역을 1로 처리해준 뒤 방문하지 않은 영역(0)에 대해서 BFS를 돌리면 된다.

BFS를 돌면서 총 몇 칸인지를 count 변수에 저장했고, 그 값을 오름차순으로 출력해주면 된다.

실버 1 난이도라기엔 쉽다.

코드

from sys import stdin
from collections import deque

input = stdin.readline

M, N, K = map(int, input().split(" "))  # M : row, N : col, 사각형 개수

graph = [[0 for _ in range(N)] for _ in range(M)]


for _ in range(K):
    lc, lr, rc, rr = map(int, input().split(" "))

    for r in range(lr, rr):
        for c in range(lc, rc):
            # 색칠
            graph[r][c] = 1

# 상 하 좌 우
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]


def bfs(sr, sc):
    count = 1
    q = deque([(sr, sc)])
    # 방문처리
    graph[sr][sc] = 2
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < M and 0 <= nc < N:
                # 색칠X 영역
                if graph[nr][nc] == 0:
                    # 방문처리
                    graph[nr][nc] = 2
                    count += 1
                    q.append((nr, nc))
    return count


answer = []
for r in range(M):
    for c in range(N):
        if graph[r][c] == 0:
            answer.append(bfs(r, c))

answer.sort()
print(len(answer))
print(" ".join(map(str, answer)))

골드5. 백준 2589 보물섬

풀이

모든 육지값에 대해서 각각 BFS를 돌려서 최대경우일때를 구해아한다.
다만 이렇게 풀면 Pypy로만 통과해서 파이썬 통과하는 경우를 구글링해봤다.

육지가 가장 끝에 있는게 아니라면 (위아래/양옆에 육지가 있다면) 절대 최대거리가 나올 수 없으므로 그 경우를 빼주면 파이썬으로도 통과가 된다!

두 가지 경우를 모두 정리해두었다.

코드 (Pypy 통과)

from sys import stdin
from collections import deque

input = stdin.readline

ROW, COL = map(int, input().split(" "))

graph = [list(input().rstrip()) for _ in range(ROW)]

# 상하좌우
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]


def bfs(sr, sc):
    visit = [[-1 for _ in range(COL)] for _ in range(ROW)]
    max_val = -int(1e9)
    q = deque([(sr, sc)])
    visit[sr][sc] = 0
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < ROW and 0 <= nc < COL:
                if graph[nr][nc] == "L" and visit[nr][nc] == -1:
                    visit[nr][nc] = visit[r][c] + 1
                    max_val = max(visit[nr][nc], max_val)
                    q.append((nr, nc))
    return max_val


answer = -int(1e9)
for r in range(ROW):
    for c in range(COL):
        if graph[r][c] == "L":
            answer = max(answer, bfs(r, c))

print(answer)

코드 (파이썬 통과!)

from sys import stdin
from collections import deque

input = stdin.readline

ROW, COL = map(int, input().split(" "))

graph = [list(input().rstrip()) for _ in range(ROW)]

# 상하좌우
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]


def bfs(sr, sc):
    visit = [[-1 for _ in range(COL)] for _ in range(ROW)]
    max_val = -int(1e9)
    q = deque([(sr, sc)])
    visit[sr][sc] = 0
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < ROW and 0 <= nc < COL:
                if graph[nr][nc] == "L" and visit[nr][nc] == -1:
                    visit[nr][nc] = visit[r][c] + 1
                    max_val = max(visit[nr][nc], max_val)
                    q.append((nr, nc))
    return max_val


answer = -int(1e9)
for r in range(ROW):
    for c in range(COL):
        if graph[r][c] == "L":
            # 위아래가 육지라면
            if 0 <= r - 1 < ROW and 0 <= r + 1 < ROW:
                if graph[r - 1][c] == "L" and graph[r + 1][c] == "L":
                    continue
            # 양옆이 육지라면
            if 0 <= c - 1 < COL and 0 <= c + 1 < COL:
                if graph[r][c - 1] == "L" and graph[r][c + 1] == "L":
                    continue
            answer = max(answer, bfs(r, c))

print(answer)