우주의 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를 출력하면 끝.

from collections import deque
n = int(input())
matrix = [(list(map(int, input().split()))) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

queue = deque()
queue.append((0, 0))

while queue:
    x, y = queue.popleft()
    visited[x][y] = True
    jump_size = matrix[x][y]
    dx = [0, jump_size]
    dy = [jump_size, 0]

    for i in range(2):
        nx = dx[i] + x
        ny = dy[i] + y

        if n <= nx or n <= ny:
            continue
        if jump_size == 0:
            continue
        if jump_size == -1:
            print("HaruHaru")
            exit(0)
        if not visited[nx][ny]:
            queue.append((nx, ny))
            visited[nx][ny] = True

print("Hing")

https://universe-lee.tistory.com/34

점프왕 쩰리 (small)의 다음편 large이다. 주어진 맵의 크기가 2에서 64로 올라가는데,

이를 메모리나 시간 초과 없이 푸는게 관건이다.

따라서 bfs시에 이미 갔던 길을 계속해서 가게 된다면 결국 도착 하기 전에 시간초과나 메모리 낭비가 생길것이니

이미 갔던 길을 표시하여, 아 여기는 안 갈래! 하면 되는것이다.

visited 라는 리스트를 만들고, bfs시마다 현재 좌표에 일종의 flag를 꽂는다 (방문, 미방문)

나중에 queue에 새로운 위치를 넣을 때 이미 방문한 위치라면 (visited == True) 재 방문하지 않는다.,

from collections import deque
n = int(input())
matrix = [(list(map(int, input().split()))) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

queue = deque()
queue.append((0, 0))

while queue:
    x, y = queue.popleft()
    visited[x][y] = True
    jump_size = matrix[x][y]
    dx = [0, jump_size]
    dy = [jump_size, 0]

    for i in range(2):
        nx = dx[i] + x
        ny = dy[i] + y

        if n <= nx or n <= ny:
            continue
        if jump_size == 0:
            continue
        if jump_size == -1:
            print("HaruHaru")
            exit(0)
        if not visited[nx][ny]:
            queue.append((nx, ny))
            visited[nx][ny] = True

print("Hing")

from collections import deque
n = int(input())
matrix = [(list(map(int, input().split()))) for _ in range(n)]
queue = deque()
queue.append((0, 0))

while queue:
    x, y = queue.popleft()
    jump_size = matrix[x][y]
    dx = [0, jump_size]
    dy = [jump_size, 0]

    for i in range(2):
        nx = dx[i] + x
        ny = dy[i] + y

        if n <= nx or n <= ny:
            continue
        if jump_size == 0:
            continue
        if jump_size == -1:
            print("HaruHaru")
            exit(0)
        queue.append((nx, ny))

print("Hing")

bfs를 통해 이동가능한 모든 경우(우, 하)를 대입시켜 목적지에 도달할 경우

haruharu를, 그렇지 않을 경우 hing을 출력시킨다.