본문 바로가기

Algorithm 💡/DFS28

[소프티어 6275번] 로봇이 지나간 경로(HSAT 1회 정기 코딩 인증평가 기출) Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.aiimport sysinput = sys.stdin.readlinedx, dy = [-1,1,0,0], [0,0,-1,1]# L : 왼쪽으로 90도 회전# R : 오른쪽으로 90도 회전# A : 로봇이 바라보는 방향으로 2칸 전진(범위를 벗어나면 수행X)# 같은 칸을 2번 이상 방문하지 못하도록 명령# 출발지점을 포함한 로봇이 방문한 모든 칸을 지도에 표시# 로봇이 지도에 사수에 표시한 모든 칸들만을 방문하도록 조작# 1. 처음 로봇을 어떤 칸에, 어떤 방향으로 두어야 하는가 ?# 2. 이후 로봇에 어떤 명령어를 순서대로 입력해야 하는가 ?# 입력하는 명령어의 개수를 최소화 했을때 [첫번째 로봇의 위치 좌표], [방향], [명령어]h, w.. 2024. 6. 27.
[소프티어 7727번] 함께하는 효도 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.aiimport sysinput = sys.stdin.readline# m명의 친구를 불러 나무에서 열매를 수확# n x n 크기의 격자에 모든 칸에 나무가 심어져있고, 각 나무마다 가능한 열매 수확량이 주어져 있음# 친구들은 서로 다른 위치에서 출발하여 1초에 1칸씩 상하좌우로 움직임# 최종적으로 모든 열매 수확량의 합을 최대로 만들고자 함# 한 나무에 여러 친구가 방문하게 되더라도 열매는 딱 한번만 수확 가능# 또한, 친구들끼리 이동하는 도중 만나는 것도 가능# m명의 친구들이 3초동안 최대로 얻을 수 있는 열매 수확량의 총합n, m = map(int,input().split())area = [list(map(int,input().spl.. 2024. 6. 24.
[소프티어 6246번] 순서대로 방문하기(HSAT 7회 정기 코딩 인증평가 기출) Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai import sysfrom collections import deque# 0 - 빈칸, 1 - 벽# 이동은 상하좌우 중 인접한 칸만 가능# 한번 지났던 지점은 다시 방문 X# 방문해야 하는 지점의 첫 지점이 출발점, 마지막 지점이 도착점# 순서대로 방문해야 하는 칸을 이동하는 시나리오 수input = sys.stdin.readlinen, m = map(int,input().split())area = [list(map(int,input().split())) for _ in range(n)]visited = [[False]*n for _ in range(n)]visit_list = [] # 방문해야 하는 지점들을 저장하는 배열answer .. 2024. 6. 18.
[소프티어 6248번] 출퇴근길 # 시간 초과 코드(10/100)import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**6)# 동환이의 출퇴근 길은 1~n까지 번호가 매겨진 단방향 그래프# m개의 일방통행 도로가 존재# 동환이의 집과 회사는 각각 정점 S, T로 나타냄 (출퇴근길은 S와 T 사이의 경로)# S에서 T로 가는 출근 경로와 T에서 S로 가는 퇴근 경로에 모두 포함될 수 있는 정점의 개수# 단, 출퇴근길에서 목적지 정점을 방문하고 나면 동환이는 더 이상 움직이지 않는다.# 즉, 출근길 경로에 T는 마지막에 정확히 1번만 등장하며 퇴근길 경로도 마찬가지로 S는 마지막에 1번만 등장# (대신 출근길에 S와 퇴근길에 T와 같이 출발지점은 여러번 등장해도 됨)n, m = map.. 2024. 6. 15.
[백준 1240번] 노드사이의 거리 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net from collections import deque n,m = map(int,input().split()) graph = [[] for _ in range(n+1)] for _ in range(n-1): # n-1개의 간선을 입력받고, 양방향으로 저장 start, end, distance = map(int,input().split()) graph[start].append((end,distance)) graph[end].append((star.. 2024. 1. 8.
[프로그래머스 PCCP 모의고사 2-4번] 수레 def solution(maze): answer = 0 n = len(maze) m = len(maze[0]) dx = [-1,1,0,0] dy = [0,0,-1,1] minimum = float("inf") is_success = False # 모든 수레가 각각의 도착 칸에 이동해야 함 # 각 턴 마다 모든 수레를 상하좌우로 인접한 칸 중에 하나로 이동 # 벽(5)이나 격자 판 밖으로 이동 X # 자신이 방문했던 칸으로 이동 X # 도착 칸에 위치한 수레는 더 이상 이동 X # 동시에 두 수레를 같은 칸에 위치 X # 수레끼리 자리를 바꿀 수 X for i in range(n): for j in range(m): if maze[i][j] == 1: red_start = (i,j) if maze[i][j.. 2023. 11. 18.