N-queen [백준 9663]
1. 문제 접근 방법 - DFS를 기본적으로 활용하는 문제이다. -> DFS를 활용하되, 각각의 행마다 열을 하나씩 선택해주면 된다. -> 이 때, 열을 중복해서 선택하지 않고, 또한, 기존에 선택한 점들과 대각선에 존재하지 않도록 하면서 선택하면 되는 문제이다. -> 이렇게 해서 row가 N+1에 도달했을 때, 정답의 개수를 1 증가시키면 되는 문제이다. 2. 코드 N = int(input()) ans = 0 def check(row, col, checked, N): for x, y in checked: if abs(x-row) == abs(y-col): return False return True def dfs(row, cols, checked, N): global ans if row == N+1: ..
마법사 상어와 파이어 스톰 [삼성 기출]
1. 문제 접근 방법 - 격자판을 나누어서, 격자판을 회전시킨 후에, 얼음의 양을 줄이는 것을 반복하는 문제이다. 이 때 중요한 것은 격자판을 정확하게 회전시키는 것이다. -> rotate 함수에 주목하자 -> rotate 함수에서 4차원 for문을 활용해서 회전을 시켰다. 2. 내 코드 from collections import deque import copy N, Q = map(int, input().split()) board = [] for i in range(2**N): row = list(map(int, input().split())) board.append(row) magics = list(map(int, input().split())) dx = [-1, 0, 1, 0] dy = [0, 1, ..
탈주범 검거 [SWEA 모의 역량 테스트]
1. 문제 접근 방법 - 이 문제 같은 경우는 bfs를 통해 board를 탐색하되, board에 있는 파이프의 종류에 따라서, 현재 지점으로부터 다음 지점이 방문 가능한지를 판단하는 것이 중요한 문제이다. -> 이 문제에서 중요한 포인트는, 현재 지점에서 다음 지점으로 방문가능한지 판단할 때, 현재 지점의 파이프 모양과 다음 지점의 파이프 모양을 같이 고려해야 한다는 점이다. -> 이 때 파이썬의 배열의 in을 잘 활용해주면 좋다. 2. 코드 from collections import deque T = int(input()) dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] def findAble(type): if type == 1: return [0, 1, 2, 3] elif type..
등산로 조성 [SWEA 모의 SW 역량 테스트]
// 1시간 반 소요 1. 문제 접근 방법 - SWEA에서 문제를 풀 때, 전체 다 지우고, 내가 사용할 것들을 넣으면 된다 -> 또한, for 문 같은 경우는 있는 그대로 사용하려면, 그 양식에 맞게 사용해야 한다 - 문제를 DFS로 접근했다 -> DFS로 접근할 때, 테스트 케이스를 잘 고려해야 한다 -> 특히, 중요한 것이 최대 K만큼 팔 수 있다는 것을 어떻게 반영할지이다. -> 최대 K만큼 팔 수 있고, K-1, K-2... 도 팔 수 있으나, 최소한, 현재 칸보다는 하나 작게 만들때까지는 파야 한다. 왜냐면 팠는데, 현재 칸과 같거나 현재 칸보다 높다면, 이동이 불가능하기 때문이다. 이 점을 잘 고려해야 한다 - if K>=gap이라는 조건도 중요하다. 왜냐하면 이 조건이 있어야만, 다음 방문..
벽 부수고 이동하기 [백준 2206]
1. 문제 접근 방법 - 이 문제는 문제를 풀다가 막혀서 구글링해서 참고했다 구글링을 통해서, visited 배열을 3차원 배열로 선언해서, 벽을 깬 케이스와 벽을 깨지 않은 케이스를 구분해서 접근할 수 있음을 알게 되었다. 이러한 접근법을 학습하게 되었고, 다른 문제를 푸는데 응용해봐야겠다. from collections import deque N, M = map(int, input().split()) board = [] visited = [[[0]*2 for _ in range(M)] for _ in range(N)] dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] for i in range(N): row = input() tmp = [] for j in range(M): tmp...
안전 영역 [백준 2468]
1. 문제 접근 방법 - BFS, DFS 중에서 파이썬에서는 왠만하면 BFS를 쓰도록 하자 - 이 문제는 visited 배열의 선언이 필요한데, 이 배열을 for문 안에 쓰면 메모리 초과가 발생한다 -> 전역적으로 선언해서 재활용하도록 하자 - 아예 물에 안 잠기는 경우, 즉, maxHeight가 0인 경우가 존재함을 알아야 한다 2. 코드 from collections import deque N = int(input()) board = [] visited = [[False]*N for _ in range(N)] dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] for i in range(N): row = list(map(int, input().split())) board.append(..