99클럽 코테 스터디
어제까지만 하고 접으려고 했는데, 스터디 오픈카톡방에서 누가 문제 링크달라고 해서 들어갔다가 권장 4시간인거 보고 승부욕이 생겨 풀었다.
접으려던 이유 중 가장 큰 건, TIL 적는데 너무 오래걸려서(보통 문제 푸는 시간의 2배쯤?) 였는데, 이젠 진짜진짜로 TIL은 대충만 쓸 것이다. 아무리 오래 걸려도 20분 이내를 목표로? 문제도 그냥 어지간하면 챌린저 문제만 풀려고 한다.
원랜 TIL을 자세히 열심히 읽으면 누구나 풀이를 이해할 수 있을 정도로 풀어서 썼다면, 이제는 그냥 될대로 되란 식? 이걸 읽는 누군가가 있다면 서운해도 어쩔수 없다. 내 맘이니까 하하
수정 : 미들러 문제도 풀고 추가
챌린저 문제 방의 개수 : https://school.programmers.co.kr/learn/courses/30/lessons/49190
미들러 문제 가장 먼 노드 : https://school.programmers.co.kr/learn/courses/30/lessons/49189
출처 : 프로그래머스
챌린저 문제 : 방의 개수
풀이 접근
이미 탐색했던 점을 또 방문하고, 그게 이미 탐색했던 그래프가 아닌 다른 그래프로 들어가는 것이라면, 다각형 한 개가 완성된다.
여기까지만 적용하면 테스트케이스 한 갠가 두개만 맞는다.
대각선끼리는 교차될 수 있기 때문에, 대각선 이동은 절반씩 잘라서 두 번 이동하는 것으로 바꾸면 통과된다. 이 방식 말고 그냥 예외처리를 직접 하려고 하면 머리통이 깨질 것이다. 그림판에 몇 가지 경우를 그려봤는데, 이건 말이 안 된다.
이 아름다운 풀이를 남들과 아주 자세히 공유하고 싶지만, 그러면 또 한두시간이 삭제될 것이라서 참겠다. 코드를 보고 최대한 이해해 보시길...
코드(Python3, 통과, 최대 177.01ms, 63.7MB)
수평, 수직 이동은 2씩 이동, 대각 이동은 1씩 두번 이동으로 하면 된다.
x, y는 현재 위치의 좌표이다.
if (x + dx, y + dy) in points and (x, y, x + dx, y + dy) not in graphs:
라는 조건을 만족하면 닫힌 다각형이 완성된 것이다.
graphs에 간선을 넣을 때는, 양방향을 다 고려하기 위해 반대 방향도 같이 넣는다.
이 문제는 무한한 평면 위에서 진행되고, 10만 번 이동하면 도달할 수 있는 칸의 개수가 20만^2 = 400억 개이기 때문에, visited로 하면 당연히 안 되고, 파이썬의 set과 같은 자료구조를 이용해야 한다. (인덱스가 없는 대신 삽입과 탐색이 모두 O(1))
def solution(arrows):
answer = 0
graphs = set()
points = {(0, 0)}
x = 0
y = 0
directions = ((0, 2), (1, 1), (2, 0), (1, -1), (0, -2), (-1, -1), (-2, 0), (-1, 1))
for arrow in arrows:
dx, dy = directions[arrow]
if (x + dx, y + dy) in points and (x, y, x + dx, y + dy) not in graphs:
answer += 1
graphs.add((x, y, x + dx, y + dy))
graphs.add((x + dx, y + dy, x, y))
x += dx
y += dy
points.add((x, y))
if dx and dy:
if (x + dx, y + dy) in points and (x, y, x + dx, y + dy) not in graphs:
answer += 1
graphs.add((x, y, x + dx, y + dy))
graphs.add((x + dx, y + dy, x, y))
x += dx
y += dy
points.add((x, y))
return answer미들러 문제 : 가장 먼 노드
풀이 접근
bfs 문제이다.
더 이상 아직 방문 안한 노드로 갈 수 없을 때까지 bfs 탐색하고, 마지막에 있는 노드의 개수를 반환하면 된다.
코드(Python3, 통과, 최대 35.12ms, 23.1MB)
나는 파이썬으로 bfs할 때 set 자료구조를 자주 쓴다.
그리고, edge가 저런 형식으로 들어올 때 connected 리스트를 만든 것처럼 이차원 리스트 형태로 다시 바꿔서 사용할 때가 많다.
문제 조건 중에 모든 노드가 연결되어 있다는 보장이 없으므로, if not farther:
이 확인을 안 하면 far이 비어 있는 채로 while문을 영원히 돌 수도 있음에 유의한다.
def solution(n, edge):
not_visited = {i for i in range(2, n + 1)}
connected = [[] for _ in range(n + 1)]
for a,b in edge:
connected[a].append(b)
connected[b].append(a)
far = {1}
while not_visited:
farther = set()
for node in far:
for c in connected[node]:
if c in not_visited:
farther.add(c)
not_visited.remove(c)
if not farther:
return len(far)
far = farther
return len(far)