우주의 IT 소행성

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을 출력시킨다.

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

n, k = map(int, input().split())
graph = [] # 그래프 정보를 담는 리스트
data = [] # 바이러스 정보를 담는 리스트

for i in range(n):
    graph.append(list(map(int, input().split())))
    for j in range(n):
        # 바이러스가 있는 경우
        if graph[i][j] != 0:
            data.append((graph[i][j], 0, i, j))

data.sort()
queue = deque(data)
t_s, t_x, t_y = map(int, input().split())

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

while queue:
    virus, s, x, y = queue.popleft()
    # 정확히 s초가 지나거나 큐가 빌 때 까지 반복
    if s == t_s:
        break

    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y
        # 해당 위치로 이동할 수 있는 경우
        if 0 <= nx and nx < n and 0 <= ny and ny < n:
            #아직 방문하지 않았다면 그 위치에 바이러스 넣기
            if graph[nx][ny] == 0:
                graph[nx][ny] = virus
                queue.append((virus, s + 1, nx, ny))
print(graph[t_x - 1][t_y - 1])

BFS로 해결할 수 있는 문제.

맵과 바이러스에 대한 정보를 따로 받는게 핵심이다.

바이러스의 숫자가 낮은 종류부터 먼저 전염을 시켜야 하기 떄문이다.

따라서 맵을 한 줄 한 줄 받을 때 마다 바이러스가 있는지 여부를 체크한 후, 

바이러스가 있다면 해당 바이러스의 위치와 번호를 queue에 입력한다.

오름차순으로 정렬된 queue를 bfs시키면서 채워나가는 방식으로 문제 해결

브론즈 5에서 골드 3까지, 지금의 나를 되돌아 보는 시간을 가졌다.

문제 풀이에 재미를 느끼고, 이젠 아까 못 풀었던 문제가 다른 일을 할 때도 머릿속에 맴돈다.

티어가 실력의 지표는 아니지만, 그래도 기분이 좋은건 사실이다.

좀 더 나은 내가 될 수 있도록, 좀 더 나은 코드를, 알고리즘을 생각하고 사고할 수 있도록 노력하자

플레티넘까지 파이팅!