영호

문제 링크 https://www.acmicpc.net/problem/5427 나의 풀이 기본적으로 최소시간을 구하는 문제라 BFS를 사용했습니다. 그리고 문제를 '불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다' 라는 문장이 있습니다. 즉, 불이 먼저 동서남북으로 한 칸씩 번지게 한 다음에 상근이가 동서남북으로 움직일 수 있는지 구별해야 합니다. 구현 기능 불은 동서남북으로 한 칸씩 번져야 한다. 단, 벽에는 불이 붙을 수 없다. 상근이도 동서남북으로 한 칸씩 움직일 수 없다. 역시 벽으로는 이동할 수 없고, 불이 붙으려는 칸으로 이동할 수 없다. -> 불을 먼저 번지게 함으로써 구별 상근이가 x,y 좌표 중 하나라도 map의 가장자리에 도착하게 되면 탈출가능한 경우이다. 막혔던 점 sB..

문제 링크 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 나의 풀이 최단거리를 구하기 위해 bfs를 사용했습니다. 최대 입력이 100,000까지라 maps를 100,001 크기로 설정했습니다. bfs알고리즘을 수행하며 x+1, x-1, x*2로 탐색을 했습니다. 인덱스 에러 방지 및 방문한 지점에 대해서 예외처리를 진행합니다. deque.leftpop()에서 목표 지점과 동일한 값이 나오면 bfs()를 종료합니다...

문제 링크 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 나의 풀이 bfs를 이용해 풀었습니다. 입력 값 중 익은 토마토들을 탐색해 tomatos배열에 저장합니다. [x,y, 언제 익었는지] -> 처음부터 익은 토마들이기 때문에 처음에는 [x, y, 0]으로 저장합니다. tomatos를 이용해 queue를 생성합니다. bfs를 수행합니다. bfs는 현재 위치에 있는 토마토가 익은 위치에서만 탐색을 진행하기 때문에 if문을 이용..

문제 링크 https://www.acmicpc.net/problem/18405 나의 풀이 입력을 받으면서 초반 virus들의 정보를 [virus_num, 0(time), x, y] 별도의 list에 저장한다. virus_num이 낮은 것들부터 전염이 되기 때문에 위 list를 정렬한다. virus정보들을 담은 list를 q로 만든다. time이 끝날 때까지 bfs알고리즘을 수행한다. Code # https://www.acmicpc.net/problem/18405 from collections import deque n, k = map(int,input().split()) graph = [] virus_info = [] for i in range(n): graph.append(list(map(int,inp..

문제 링크 https://www.acmicpc.net/problem/14502 나의 풀이 방법 안전영역인 0의 좌표들을 safe_zones배열에 저장한다. 3개의 벽을 세울 안전영역 3군데를 고른다. 이때 (1,1), (2,2), (3,3)에 세우는 것과 (1,1), (3,3), (2,2)에 세우는 것은 똑같은 경우이기 때문에, combination을 사용한다. 이 작업을 하지 않으면 시간초과가 발생한다. 안전영역에 3개의 벽을 세우는 모든 경우의 수에 대해 bfs를 수행한다. Code # 연구소 import sys from collections import deque from itertools import combinations input = sys.stdin.readline row, col = map..