BFS보다는 DFS로 풀이하는게 직관적이다 보니, BFS에 대한 풀이가 아직은 익숙하지 않다... 휴..이제 좀 열심히 해야지 ㅜㅜ 어쨌든 이번에도 역시나 DFS로 풀이를 했는데 시간초과가 났다... 해당 풀이는 아래와 같다. def dfs(loc, curTime): global minTime if loc == [N-1, M-1]: minTime = min(minTime, curTime) return chk = False for i in range(4): nx = loc[0]+dx[i]; ny = loc[1]+dy[i] if 0

처음에 텍스트 만으로는 이해하기 어려워서 아래 그림과 같이 그려가며 이해해보았다. # R연산 : 배열 A의 모든 행에 대해서 정렬을 수행 -> 행의 개수 >= 열의 개수 # C연산 : 배열 A의 모든 열에 대해서 정렬을 수행 -> 행의 개수 < 열의 개수 def rowSort(graph): copyGraph = [] maxRowLen = 0 for rowGraph in graph: srGraph = set(rowGraph) lrGraph = list(srGraph) lrGraph.sort(reverse=True) tmp = [] for i in range(len(lrGraph)): if lrGraph[i] == 0: continue tmp.append([lrGraph[i], rowGraph.count(l..

이번 문제는 하라는대로 잘 만 하면 되는 문제다. 그러나 딱 한가지 좀 시간이 걸렸던 부분이라면 상어가 더이상 갈 곳이 없으면 반대방향으로 전환하여 계속 남은 부분을 이동하는 것이었는데 분명 수식이 있을것이라 생각하였다. 해당 수식은 sharkMove에 구현되어있다. 이것만 제외하면 생각보다 쉽게 풀려지는 문제였다. def sharkMove(x, y, s, d): # print("-----------------------" + str(x) + ', ' + str(y) + "-------------------------------") # 1 : 위 , 2 : 아래, 3 : 오른쪽, 4 : 왼쪽 dx = [0, -1, 1, 0, 0] dy = [0, 0, 0, 1, -1] nx = x + (dx[d] * s..

Point 1 0: x좌표가 증가하는 방향 (→) 1: y좌표가 감소하는 방향 (↑) 2: x좌표가 감소하는 방향 (←) 3: y좌표가 증가하는 방향 (↓) * 일반적으로는 y는 가로로 증가 또는 감소하며, x는 세로로 증가 또는 감소한다. 하지만 이 문제에서는 x가 가로 방향으로 증가 또는 감소하며, y가 세로 방향으로 증가 또는 감소하는 것으로 정의하였다. Point 2 0 세대 1 세대 2세대 3세대 위의 그림과 같이 세대별 방향을 보면 이전 세대의 역순 + 1 이라는 규칙성을 발견할 수 있다. 0세대 0 1세대 0 + 1 2세대 0, 1 + 2, 1 3세대 0, 1, 2, 1 + 2, 3, 2, 1 from copy import deepcopy dx = [0, -1, 0, 1] dy = [1, 0..

다음은 테스트케이스 4번을 대상으로 시각화한 것이다. from collections import deque N, L, R = map(int, input().split()) graph = [] for _ in range(N): temp = list(map(int, input().split())) graph.append(temp) dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] result = 0 def bfs(ox, oy, curNum): global union, L, R, graph # 연결되어있는 영역을 모아둔 리스트 connectedList =[] connectedList.append((ox, oy)) # 경계를 확장 할 수 있는 영역들이 q에 들어오면서 최대 어디까지 뻗어갈 수 ..

이 문제 풀이를 보니 bfs, dp로 푼사람들이 많던데... 아직 bfs로 생각하는 로직이 익숙하지 않다보니 무지성으로 dfs로 풀어버렸다. bfs, dp에 대한 익숙도를 높일 필요가 있어보인다. 어쨌든 처음에 TC를 통과하고 나서 제출하니 시간초과가 나왔다. 정말 시간초과가 제일 싫은게...논리적으로는 다 맞는데 여기서 효율성까지 따져야하니 어디서 고쳐야할지 아직은 감이 안 선다. ㅎㅎㅎ 일단 아래 코드는 통과한 코드이며, 시간초과를 해결한 방법 3가지를 정리해보았다. 시간초과 원인 1 dfs에서 모든 경우의 수를 탐색하다가 시간초과 나는 것을 방지하고자, 만약 문제에서 요구하는 "n번 시작 = n번 종료"인 경우에는 result를 True로 두고 더 이상 depth를 높여 탐색하지 않도록 하였다. 시..