분류 전체보기

[구현] BOJ 21610 마법사 상어와 비바라기

간단히 지시사항을 따르면 되는 문제. 주의해야할 부분이라면 구름이 존재했던 위치를 일일이 리스트로 찾게되면 시간초과가 난다는 점이다. visited 리스트를 매번 새로 생성해서 그 위치에 구름이 있었는지 확인하는게 더 시간이 적게 든다. https://www.acmicpc.net/problem/21610 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 from collections import deque import sys input = sys.stdin...

빈출 유형

보호되어 있는 글입니다.

행렬 회전 자료

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 # clockwise 90 : 전치 -> 좌우반전 # clockwise 180 : 좌우반전 -> 상하반전 # clockwise 270 : 전치 -> 상하반전 # counterwise 90 : 전치 -> 상하반전 # counterwise 180 : 상하반전 -> 좌우반전 # co..

[구현] BOJ 21608 상어 초등학교

시작점 때문에 시간이 걸렸던 문제. 그림만 보면 헷갈리는데 시작점도 1,2,3번 조건에 해당하는 지점을 선택하도록 해야 문제를 맞출 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 from typing import List, Dict, Set N = int(input()) board..

[BFS, 시뮬레이션, 배열 회전] BOJ 20058 마법사 상어와 파이어스톰

2차원 배열 회전 방식을 알고 있어야 풀 수 있는 문제. 해당 문제는 시계방향 90도지만 180, 270 + 반시계방향에 대해서도 숙지하는 것이 좋을 것 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 from typing import List from collections import deque N, Q = map(int, inpu..

[큐, 시뮬레이션] BOJ 3190 뱀

https://www.acmicpc.net/problem/3190 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 import sys from collections import deque input = sys.stdin.readline N = int(input()) K = int(input()) board = [[0] * N for _ in range(N)] apples = [list(map(int, input().split())) for _ in range(K)] DELTAS = deque([(0, 1..

[BFS, 시뮬레이션] 14500 테트로미노

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 import sys input = sys.stdin.readline N, M = map(int, input().split()) board..

[백트래킹, BFS] BOJ 19236 청소년 상어

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 괜히 기교부리려고 했다가 왜맞틀 했던 문제. 정직하게 푸는게 best다 주의할 점은 board와 states로 재귀함수를 호출할때 꼭 복사하자는 것.

[시뮬레이션] BOJ 20057 마법사 상어와 토네이도

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677import sysfrom typing import List, Tuplefrom collections import dequeinput = sys.stdin.readline N = int(input())board = [list(map(int, input().split())) for _ in range(N)] deltas = deque([(0, -1), (1, 0), (0, 1), (-1, 0)]) def update_board(board:List[Li..

[시뮬레이션, BFS] BOJ 16236 아기상어

https://www.acmicpc.net/problem/16236 시뮬레이션 + dfs + dp(visited) 살짝 가미된 형태로 구현하였다. 여기서 주의할 점은 잡아먹는 물고기의 크기는 1 ~ 6이라면 커지는 상어의 크기는 무한하다는 것. size로 제한하면 초반엔 괜찮지만 상어의 크기가 9이상이 되면 무한 반복이 일어나 시간초과가 발생할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 ..

[시뮬레이션] BOJ 16234 인구이동

graph를 구성하고 graph 탐색하는 방식으로 구현. 이때 주의할 점은 graph를 만들때 왼, 오, 위, 아래 모두 확인해서 넣어야한다는 점. 그다음에 visited로 제외해야하는 방식이 예외케이스를 만들지 않는다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 import sys from typing..

[시뮬레이션] BOJ 15683 감시

시계방향으로 움직이기 위해 (위, 오, 아래, 왼)의 시계방향 queue를 설정 주의할 점 : 모든 cctv는 어짜피 사용하기 때문에 각 cctv는 depth로 접근하면 됨 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 import sys from copy import deepcopy from typing import List fro..