문제 5014 - 스타트링크 접근 1차원 BFS 문제이다. 위, 아래로만 이동할 수 있는 1차원 선에서 움직인다고 생각하면 된다. 역시 BFS는 몇 번만에 해당 지점에 도착했는지 파악이 쉽고, 처음 도착했을 때 횟수가 최소임을 보장받는다. 코드 파이썬 코드 from collections import deque def ...

문제 7562 - 나이트의 이동 접근 BFS 문제이다. 단지 기존에는 2차원 공간에서 상하좌우로 움직였다면, 여기서는 조금 변형해서 8 곳으로 이동할 수 있다는 것만 다르다. 코드 파이썬 코드 from collections import deque def bfs(sx, sy, ex, ey): dx = [-2,-2,...

문제 7576 - 토마토 접근 BFS 문제이다. 따로 방문배열을 사용할 필요가 없어서 Board 하나로만 이용했다. BFS의 가장 편한 점은 일반적인 경우에 최초 방문한 지점은 항상 최단 거리로 방문했음을 확신할 수 있다. 때문에 최초 방문만 신경써서 처리해주면, 이미 방문한 지점에 대해서는 따로 고민할 필요가 없다. 코드 ...

Contents Feature Engineering 정형 데이터 정규화(Normalization) 수치형 데이터 Min-Max Scaling Z-score Normalization 범주형 데이터 ...

문제 2206 - 벽 부수고 이동하기 접근 조금 까다로웠던 것 같다. BFS로 푸는 건 맞는 것 같은데, 벽을 최대 한개까지는 부술 수 있다. 이걸 어떻게 처리해줄지 고민했던 문제이다. 생각보다 단순하게 풀 수 있었는데, 기존에는 벽이 아닌 경우에만 queue에 좌표를 추가해주었다. 여기서는 queue에 현재 좌표와 벽을 부쉈는지를...

문제 3055 - 탈출 접근 앞에서 풀었던 불 문제와 유사하다. 다른 점은 종료 조건이다. 앞에선 판을 벗어날 수 있으면 종료했지만, 여기서는 종료 지점이 정해져 있다. 주의할 점은 종료지점에는 물이 차지않는다! 코드 파이썬 코드 from collections import deque import sys dx = [0...

문제 5427 - 불 접근 2차원 공간에서 최단 경로를 찾아야 한다. 특이한 점은 불이라는 존재이다. 상근이가 1초마다 한 칸을 움직일 수 있듯이 불도 1초마다 인접한 칸으로 전파된다. 매 초 불길이 전파되고, 이러한 불에 닿지 않고 출구까지 가는 방법을 찾아야 한다. 상근이와 불을 동시에 생각하지 않으면 쉬워질 것 같다. 우선 ...

문제 1743 - 음식물 피하기 접근 2차원 공간에서 영역의 개수를 찾는 문제이다. 배추가 심어져 있는 1의 칸 중에 방문하지 않은 칸에 대하여 BFS를 수행한다. BFS를 수행한 횟수가 영역의 개수이다. 코드 파이썬 코드 import sys from collections import deque dx = [0,0,-1,...

문제 1012 - 유기농 배추 접근 2차원 공간에서 영역의 개수를 찾는 문제이다. 배추가 심어져 있는 1의 칸 중에 방문하지 않은 칸에 대하여 BFS를 수행한다. BFS를 수행한 횟수가 영역의 개수이다. 코드 파이썬 코드 import sys from collections import deque dx = [0,0,-1,1...

문제 6593 - 미로 탐색 접근 2차원 BFS 문제에서 3차원으로 차원만 늘린 경우이다. 2차원일 때는 인접한 4칸을 확인했다면, 3차원일 때는 인접한 6칸을 확인하면 된다. 이 때 방문배열인 visit를 -1로 초기화하고 시작한다면 종료지점에 도달할 수 있는지 없는지에 대한 검사가 필요없어진다. 이 문제의 경우는 출력 형식이 다르...