[swea] 4615 재미있는 오셀로 게임
재미있는 문제라서 들고 왔습니다. 1. 해당 방향으로 쭉 탐색하면서 해당 칸 놓는 돌로 변경. 2.1 만약 끝에 같은 돌이 없다면, 다시 원래대로. 2.2 만약 끝에 같은 돌이 있다면, 그대로 유지 dfs를 이용해서 풀었습니다. t = int(input()) directions = [[0,1],[0,-1], [1,0],[-1,0],[1,1],[-1,-1],[1,-1],[-1,1]] def dfs(board, y,x, dy, dx, c, n): if y = n or x >= n: return True if board[y][x] == 0: return True if board[y][x] == c and board[y][x] != 0: return False tmp = boa..
2023. 5. 20.
[다익스트라] 백준 9370
이번 문제는 다익스트라를 통해 풀었다. 원래 처음에는 경로를 추적할 수 있도록, 거리를 측정하는 배열에 [이전 노드, 거리] 값을 저장하도록 했었다. 문제는 다익스트라는 해당 노드까지 최단거리로 갈 수 있는 경로가 많은 경우, g와 h를 포함하지 않을 수 있기 때문에 문제가 되었다. 그래서 s -> g -> h -> 목적지, s -> h -> g -> 목적지를 구하기 위해, s ,g, h를 시작점으로 각각 다익스트라 통해 최단 거리를 구한다. import heapq import sys from collections import deque def djk(board, s, n): hq = [] dst = deque([987654321 for _ in range(n+1)]) heapq.heappush(hq, ..
2023. 1. 29.
[다익스트라] 백준 레이저 통신
이번 문제는 백준 6087 레이저 통신 문제입니다. 다익스트라를 이용해서 풀었습니다. 각 지점의 최소거리(거울 개수)를 구하고, 이를 이용하여 또 다른 레이저 좌표까지 탐색하도록 했습니다. 중요한 점은 이전에 어떤 방향으로 진행했는지 알아야 합니다. 그래야지 거울 개수를 알 수 있기 때문입니다. import heapq def dij(razer_pos, board, r, c): hq = [] direction = {} direction['up'] = {'up':(1,0), 'left':(0,-1), 'right' : (0,1)} direction['down'] = {'down':(-1,0), 'left':(0,-1), 'right' : (0,1)} direction['left'] = {'left' : (0..
2022. 12. 25.
