반응형

dfs 6

[백준 자바] 16173번 점프왕 쩰리(small)

문제쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.‘쩰리’는 가로와 세로의 칸수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다.‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다. 위쪽과 왼쪽으로는 이동할 수 없다.‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다.‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는 칸에 쓰여 있..

[백준 3184 자바] 양

3184번 양문제미키의 뒷마당에는 특정 수의 양이 있다. 늑대는 마당에 들어와 양을 공격했다.마당은 행과 열로 이루어진 직사각형 모양이다.글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리, 'o'는 양 'v'는 늑대를 의미한다.한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면 두 칸은 같은 영역 안에 속해 있다고 한다.마당에서 탈출 할 수 있는 칸은 어떤 영역에도 속하지 않는다고 간주한다. 양은 늑대에게 싸움을 걸 수 있고 영역 안에 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서 쫓아낸다.그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다.맨 처음 모든 양과 늑대는 마당 안 영역에 존재한다.아침이 도달했을 때 살아남은 양과 늑대의 수를 출..

[백준 16964 파이썬] DFS 스페셜 저지

백준 16964 파이썬DFS 스페셜 저지문제BOJ에서 정답이 여러 가지인 경우에는 스페셜 저지를 사용 한다.스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식이다.오늘은 스페셜 저지 코드를 하나 만들어 보려고 한다.정점의 개수 N이고 정점에 1부터 N까지 번호가 매겨져 있는 양방향 그래프가 있을 때, DFS 알고리즘은 다음과 같은 형태로 이루어져 있다.이 문제에서 시작 정점은 1이기 때문에 가장 처음에 호출하는 함수는 dfs(1)이다.DFS 방문 순서는 dfs 함수에서 //x를 방문이라고 적힌 곳에 도착한 정점 번호를 순서대로 나열한 것이다.트리가 주어졌을 때, 올바른 DFS 방문 순서인지 구하여라.입력첫째 줄에 정점수 N 이 주어진다.둘째 줄부터는 N-1개의 줄에는 트리..

[파이썬 삼성sw] 6057 그래프의 삼각형

[파이썬 삼성sw] 6057 그래프의 삼각형문제정점이 N개, 간선이 M개 있는 그래프가 주어진다. 정점에는 1번에서 N번까지의 번호가 붙어 있다.이때 i 번 정점과 j 번 정점 사이에, j번 정점과 k번 정점 사이에, k번 정점과 i번 정점 사이에 모든 간선이 있는(i, j, k)를 삼각형이라고 하자 (i 이때 삼각형 개수를 구하는 프로그램을 작성하라.입력첫 번째 줄에 테스트 케이스의 수 T 가 주어진다.각 테스트 케이스의 첫 번째 줄에는 두정수 N, M이 공백으로 구분되어 주어진다.다음 M개의 줄에는 두 정수 X, Y가 주어진다.이는 X번 정점과 Y번 정점 사이에 간선이 있다는 의미이다.출력삼각형의 개수를 출력한다.풀이나는 DFS를 이용하여 풀었다.1번 정점에서부터 시작해서 1번 정점에서 연결된 모든 ..

[삼성 sw 파이썬] 2814 최장 경로

[삼성 sw 파이썬] 2814 최장 경로문제N개의 정점과 M개의 간선으로 구성된 가중치가 없는 무방향 그래프에서 최장 경로의 길이를 계산하자.정점의 번호 1부터 N번까지 순서대로 부여된다.경로에는 같은 정점의 번호가 2번 이상 등장할 수 없다 경로 상의 인접한 점들 사이에는 반드시 간선이 존재한다.경로의 길이는 경로 상에 등장하는 정점의 개수를 나타낸다. 입력첫 줄에는 테스트케이스가 주어진다.각 테스트 케이이스의 첫 번 줄에는 두 개의 자연수 N, M이 주어진다.두 번째 줄부터 M개의 줄에 걸쳐서 그래프의 간선 정보를 나타낸다.풀이문제에서 가중치가 없는 무방향 그래프라고 주어졌으면 경로상의 가장 경로를 탐색하는 완전 탐색 문제로DFS나  BFS를 이용아여 문제를 풀 수 있다.나는 DFS르 이용하여 문제를..

[백준 파이썬] 1389 케빈 베이컨의 6단계 법칙

[백준 파이썬] 1389 케빈 베이컨의 6단계 법칙 문제케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다.케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이으로 이 게임을 했을 때 모든 사람 나오는 단계의 총 합을 케빈 베이컨의 수라고 할 때 이때 이 수가 가장 적은 사람을 찾는 문제이다. 이때 단계를 계산하는 방법으로 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해 보자.1은 2까지 3을 통해 2단계 만에 연결될 수 있으며, 3까지는 1단계 , 4까지 1단계 , 5까지는 4를 통해 2단계만에 연결된다그러면 케빈 베이컨의 수는 2+1+1+2 = 6이다...

반응형