우주의 IT 소행성

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

# 좌, 우, 상, 하, 좌상대각, 우상대각, 좌하대각, 우하대각
move_x = [0, 0, -1, 1, -1, -1, 1, 1]
move_y = [-1, 1, 0, 0, -1, 1, -1, 1]


def bfs(i, j):
    graph[i][j] = 0
    queue = deque()
    queue.append((i, j))

    while queue:
        x, y = queue.popleft()
        for i in range(8):
            nx = move_x[i] + x
            ny = move_y[i] + y
            if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))

while True:
    count = 0
    w, h = map(int, input().split())
    if w == h == 0:
        break
    graph = [list(map(int, input().split())) for _ in range(h)]

    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                bfs(i, j)
                count += 1
    print(count)

1. 맵의 모든 부분을 돌면서 육지일 때 너비 우선 탐색을 실행 ( 카운트 + 1 )

2. 너비 우선 탐색시 인접한 모든 섬을 방문하여 0 으로 만듦

3. 섬이 이어지지 않을 경우 다시 1로 돌아감

4. 다시 섬을 구해서 그 섬과 이어진 부분을 전부 0 으로 만듦 ( 카운트 + 1 )

... 위를 반복해서 이어진 섬을 찾는 것

KEY POINT > 이미 탐색된 섬 전체를 0으로 만들어 메인에서 bfs 하지 않게 만들어야 함

from collections import deque

def bfs(s, t):
    queue = deque()
    queue.append((s, t, 0))
    visited = [-1] * (200)

    while queue:
        s, t, count = queue.popleft()
        if s <= t and visited[s] == -1:
            queue.append((s * 2, t + 3, count + 1))
            queue.append((s + 1, t, count + 1))
            if s == t:
                return count


c = int(input())
for i in range(c):
    s, t = map(int, input().split())
    print(bfs(s, t))

bfs를 통해 풀 수 있는 문제.
매 분기마다 A의 발차기를 할지, B의 발차기를 할지
모든 분기를 저장하여 가장 빠른 s == t에 도달한 count를 출력하면 끝.

def solution(name):
    minimum_move = [min(ord(i) - ord('A'), ord('Z') - ord(i) + 1) for i in name]
    i, answer = 0, 0
    while True:
        answer += minimum_move[i]
        minimum_move[i] = 0
        if sum(minimum_move) == 0:
            break
        l, r = 1, 1
        while minimum_move[i - l] == 0:
            l += 1
        while minimum_move[i + r] == 0:
            r += 1
        answer += l if l < r else r
        i += -l if l < r else r
    return answer

print(solution(input()))

일단 아스키코드 ord함수를 이용해 A부터 Z까지 해당 문자를 오름차순/내림차순 중 빠른 루트를 선택한다.

모든 문자들의 필요 횟수를 리스트에 담아둔 후 이동할 때 마다 해당 루트 수를 0으로 만든다(잔여이동횟수 느낌)

문제는  무조건 0에서 끝 까지 가는게아니라 가다가 중간에 되돌아 가는게 더 빠를 경우도 있다는 것이다.

이를 위해 left와 right를 각각 구하여 먼저 도달하는 수를 정답에 더해주면 된다.

def solution(n, lost, reverse):
    result = 0

    # 도난을 당한 학생 리스트
    lost_list = [-99 for _ in range(n)]
    for i in lost:
        lost_list[i - 1] = i

    # 여벌을 가져온 학생 리스트
    reverse_list = [0 for _ in range(n)]
    for i in reverse:
        reverse_list[i - 1] = i

    # 여벌을 가져온 학생이 도난 당했을 경우
    for i in reverse_list:
        if i in lost:
            reverse_list[i - 1] = 0
            lost_list[i - 1] = -99

    for i in reverse_list:
        if i > 0:
            data = [-1, 1]
            for j in data:
                if i + j in lost_list:
                    lost_list[i + j - 1] = -99
                    break

    result = lost_list.count(-99)
    return result


n = int(input())
lost = list(map(int, input().split()))
reverse = list(map(int, input().split()))
print(solution(n, lost, reverse))

문제의 조건을 파악할 때
1. 여벌을 가져온 학생은 좌 우 학생에게 1벌을 빌려줄 수 있음.
2. 여벌을 가져온 학생이 도난당했을 경우도 있음
3. 여벌을 가져온 학생을 통해 최대한의 학생이(그리디) 체육복을 입을 수 있게 하라

도난/여벌 학생 리스트를 만들어 여벌 학생의 좌우를 탐색한다.
좌 우에 한 곳이라도 도난당한 학생이 있을 경우 체육복을 건내주고, 순서 마무리
마지막 카운트를 세 주면 최대 값이 나옴.

다른 사람의 코드

def solution(n, lost, reserve):
    _reserve = [r for r in reserve if r not in lost]
    _lost = [l for l in lost if l not in reserve]
    print(_reserve)
    print(_lost)

    for r in _reserve:
        f = r - 1
        b = r + 1
        if f in _lost:
            _lost.remove(f)
        elif b in _lost:
            _lost.remove(b)
    return n - len(_lost)

n = int(input())
lost = list(map(int, input().split()))
reverse = list(map(int, input().split()))
print(solution(n, lost, reverse))

front와 back을 지정하여 lost 리스트에서 하나씩 remove를 해주었다.

간결하고 깔끔한 코드가 아닐 수 없다.

나는 사실 반복문에서 특정 리스트의 원소를 remove하는 것을 별로 좋아하지 않는다.

반복 중에 리스트의 요소에 변동이 생기게 되면 인덱스 범위를 넘어서거나 반복에 문제가 생길 때가 많았기 떄문이다

하지만 이번 문제 케이스의 경우에는 반복문에서 lost의 인덱스를 통해 어떤 분기가 결정되는게 아니므로 적합하게 사용할 수 있는 것이였다. 이런 다양한 문제를 많이 풀어봐야겠다.