코딩테스트

[프로그래머스] 미로 탈출 [python]

문제 bfs로 풀면되는 문제이다. 출발점-> 레버 + 레버 -> 도착점 두 합의 최소를 구하면 된다. 코드 from collections import deque def solution(maps): answer = 0 startDot, leverDot, endDot = None, None, None for i in range(len(maps)): for j in range(len(maps[i])): if maps[i][j] == "S": startDot = (i,j) elif maps[i][j] == "L": leverDot = (i,j) elif maps[i][j] == "E": endDot = (i,j) else: continue startToLever = bfs(maps,startDot, leverD..

[프로그래머스] 혼자 놀기의 달인 [python]

문제 결국 풀어여 되는 건 간단한데, 문제가 너무 장황하다. dfs로 사이클이 있는 그래프를 찾고, 그래프의 노드의 수가 많은 것들을 곱하면 되는 문제이다. dfs로 그래프들을 모두 구한 후, sort를 하고 가장 큰 두 개를 골랐다. 그래프가 하나만 있을 수도 있기 때문에, 미리 0을 넣어서 무조건 두 개의 그래프가 생길 수 있도록 하였다. 코드 def solution(cards): global cnt answers = [0] isChecked = [False for i in range(len(cards) + 1)] for i in range(1,len(cards) + 1): cnt = 1 if isChecked[i] == False: isChecked[i] = True dfs(cards, i, isC..

[프로그래머스] 숫자 카드 나누기 [python]

문제 최대공약수를 구해서, 서로의 배열을 나눌 수 있는지 여부를 구하고 나눌 수 없다면, answer를 나눌 수 있다면, 0을 return 하는 문제이다. 최대공약수를 구할 때 나는 유클리드 호제법을 사용했다. 코드 def solution(arrayA, arrayB): answer = 0 if len(arrayA) == 1: if arrayA[0] == arrayB[0]: return 0 else: return max(arrayA[0], arrayB[0]) else: m1 = 0 m2 = 0 gcd1 = gcd(arrayA[0], arrayA[1]) gcd2 = gcd(arrayB[0], arrayB[1]) answer = max(m1,m2) for i in range(2, len(arrayA)): gc..

[프로그래머스] 무인도 여행 [python]

문제 간단한 BFS 문제였다. X가 아닌 지점에서 BFS를 돌리고, 방문 여부를 체크한 후, X가 아닌 곧 중에 방문하지 않은 곳에서 또 다시 BFS를 돌리면 된다. 코드 def solution(maps): answer = [] visited = [[False] * len(maps[i]) for i in range(len(maps))] for i in range(len(maps)): for j in range(len(maps[i])): if visited[i][j] == False and maps[i][j] != "X": answer.append(bfs(visited,i,j,maps)) if len(answer) == 0: answer.append(-1) answer.sort() return answer..

[프로그래머스] 거리두기 확인하기 [python]

문제 BFS로 문제를 풀었다,,실수가 많아서 오래 걸렸다,, 금방 풀줄 알았는데,, 코드 def solution(places): answer = [] for place in places: q = [] for i,p in enumerate(place): for j in range(len(place)): if p[j] == "P": q.append([i,j]) if len(q) == 0: answer.append(1) continue if bfs(place, q): answer.append(1) continue answer.append(0) return answer def bfs(graph, q): mX = [0,0,1,-1] mY = [1,-1,0,0] for c in q: queue = [[c[0], c..