Python
7562_나이트의 이동
https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 역시 bfs를 이용한 문제이다! 이전에 풀었던 문제들과 유형이 같다. dx,dy가 기존에 상,하,좌,우였던 것을 나이트의 이동에 맞춰서 바꿔주기만 하면 쉽게 풀 수 있다. import sys from collections import deque input = sys.stdin.readline t = int(input()) dx = [-2,-1,1,2,2,1,-1,-2] dy = [1,2,2,1,-1..
2206_벽부수고 이동하기
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이전 미로탐색과 거의 유사하다. 단, 벽을 만났을때 부쉈는지 안부쉈는지 체크해서 안부쉈을경우 부수게 체크하면 된다! from collections import deque n,m = map(int,input().split()) graph = [ list(map(int,input())) for _ in range(n) ] visited = [[[0,0] for _ in ran..
1697_숨바꼭질
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net bfs를 이용하면 풀면 된다! 처음엔 단순하게 que에 현재 점을 추가해 가면서 하려 했는데 수가 너무 커지거나 해서 시간초과나 메모리 초과가 계속해서 났다. 한번 들렀던 점은 그때가 최소이기에 두번 들리지 않고, 또한 값이 0 < x < 100000으로 정해져 있기때문에 이를 제한해두고 문제를 푸니 풀렸다. from collections import deque n,m ..
1012_유기농 배추
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이전 문제와 똑같은 유기농 배추 문제이다. 역시 이차원 그래프, visited배열, 밭의 지도를 그리고 이어져있는 밭의 개수를 새면 된다. t = int(input()) dx = [0,1,0,-1] dy = [1,0,-1,0] for _ in range(t): m,n,k = map(int,input().split()) farm = [ [ 0 for _ in range(m) ] for __ in range(n)..
2667_단지번호 붙이기
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이전의 bfs와 dfs방식을 이차원 배열로 풀어서 해결해보았더니 성공했다. 아래와 같은 순서로 차근차근 해보았다. 1. map에 해당 지도 저장 2. 2차원 그래프와 방문할 곳을 적을 visited 배열 생성 3. 그래프 작성 4. dfs함수 작성 5. map과 visited 값을 비교하면서 dfs 돌리기 6. 나온 정답값을 정렬하고 풀기 (억까조심) n = int(input()) map = [ l..
10_Text Detection(문자감지)
Text Detecction 문제란 이미지 내에 텍스트가 존재하는 영역의 위치정보를 Bounding Box로 찾는 문제들을 말한다. EAST(Efficient and Accuracy Scene Text) 2017년에 나온 모델로 Text 인식에 특화된 모델이다. 위과정을 통해서 진행된다. QUAD방식이나 RBOX 방식의 선택지가 있다. 둘의 성능차이는 크지 않은 편이다. Loss for Score Map Text Detection 의 경우 글자인 부분의 영역을 뽑아내는것이 관건이다. 그렇기 때문에 영역중에서 글자가 아닌것이 많다면, 손실률이 높다고 볼 수 있다. Intersection over Union 두박스의 크기가 같으면 같을수록 1로 생각하는 방식 locality aware non maximum ..