[BOJ] 9466. 텀 프로젝트
문제 텀 프로젝트 (https://www.acmicpc.net/problem/9466) 풀이 1. 초기접근 문제조건 해석 문제를 잘 읽어보면, 주어진 데이터를 그래프로 보고, 이 중, 싸이클 인 것만 한 팀이 되는 것을 알 수 있다. 즉, 주어진 학생의 수(노드) n개에서 싸이클이 아닌 학생(노드) 만 잡아내면 된다. 알고리즘 모든 노드를 순차적으로 탐색해야 하므로, 기본적으로 DFS 다. 간선을 따라 DFS를 진행하되, 다음 진행 노드가 이전에 방문된 적이 있다면 (visited), 그 노드부터 현재노드까지 싸이클 내에 있음을 알 수 있다. 위 방식으로, 싸이클을 발견했다면, DFS 를 종료하고, 다시 하나씩 반대방향으로 back 하며 cycle 내에 있는 노드는 팀을 이룬다는 체크를 해준다.(team..
[BOJ] 1405. 미친로봇
문제 미친로봇 (https://www.acmicpc.net/problem/1405) 풀이 1. 초기 접근 문제조건 해석 움직임, 경로에 대한 문제고, 횟수가 정해져 있다. DFS, BFS 문제. 확률을 구해야 하므로, DFS, BFS 마지막 스텝에서 지금까지 구한 확률을 모두 더해줘야겠다. 마지막 스텝에서 지금까지의 확률을 가지고있어야 하니, 인자로 지금까지의 확률을 넘겨줘야겠다. 알고리즘 BFS가 먼저 떠올라 BFS로 구현. 코드 # 동서남북 순으로 방향 저장. dxs = [0, 0, 1, -1] dys = [1, -1, 0, 0] def bfs(x, y): q = [(x, y, 1)] step = 1 answer = 0 visited = {(x, y)} while q: size = len(q) nex..