poorman

https://www.acmicpc.net/problem/1260

[알고리즘] 깊이 우선 탐색(DFSDepth First Search) 과 너비 우선 탐색(Breadth First Search)

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

해결 방안

1. DFS, BFS의 그래프 기본 클래스를 생성한다.
2. self.graph를 collections.defaultdict(list)로 dictionary를 생성하면 self.graph의 새로운 key값을 사용할 때 따로 초기화해주지 않아도 list로 자동 생성해주므로 다음과 같이 소스 코드를 간단히 작성할 수 있다.

self.graph = dict() 
if not key in self.graph: 
  self.graph[key] = [value] 
else: 
  self.graph[key].append(value) 

# collections.defaultdict 사용시 
from collections import defaultdict 
self.graph = defaultdict(list) 
self.graph[key].append(value) # new key의 경우 자동으로 리스트 생성 

3. self.node는 결과값으로 방문한 점을 순서대로 표시해줄 리스트
4. addEdge(u, v)함수는 연결되어 있는 정점들을 graph에 저장한다. 입력값의 간선은 양방향이므로 graph[u].append(v), graph[v].append[u] 양방향으로 저장한다.
5. sortEdge()함수는 graph의 각 정점에 연결된 정점들을 순서대로 정렬한다. 이 문제에서 한 정점에 여러개의 정점이 연결되어 있는 경우에 번호가 적은 점부터 방문하기 위해서 필요하다.
6. visited = defaultdict(lambda: False)정점을 방문했는지 확인하기 위해서 필요한 dictionary데이터로 2.설명에 첨언하면 visited[key]가 정의되지 않았을 때 visited[key] == False 값을 확인하는 순간에 visited[key]의 값을 자동으로 False로 초기화해준다. 실제 key를 방문하는 순간에 dictionary 값을 생성하여 확인하기 때문에 메모리 관리가 효율적으로 가능하다.
7. DFS는 DFSUtil 재귀함수를 사용하여 Deep First Search를 구현하고, BFS는 queue를 생성하여 Breadth First Search를 구현한다.

소스 코드

from collections import defaultdict 
import sys 

class GraphDFS: 
  def __init__(self): 
    self.graph = defaultdict(list) 
    self.node = [] 

  def addEdge(self, u, v): 
    self.graph[u].append(v) 
    self.graph[v].append(u) 

  def sortEdge(self): 
    for i in self.graph: 
      self.graph[i] = list(sorted(self.graph[i])) 

  def DFSUtil(self, v, visited): 
    visited[v] = True 
    self.node.append(v) 

    for i in self.graph[v]: 
      if visited[i] == False: 
        self.DFSUtil(i, visited) 

  def DFS(self, s): 
    self.sortEdge() 
    self.node = [] 

    visited = defaultdict(lambda: False) 
    self.DFSUtil(s, visited) 

    return self.node 

class GraphBFS: 
  def __init__(self): 
    self.graph = defaultdict(list) 

  def addEdge(self, u, v): 
    self.graph[u].append(v) 
    self.graph[v].append(u) 

  def sortEdge(self): 
    for i in self.graph: 
      self.graph[i] = list(sorted(self.graph[i])) 

  def BFS(self, s): 
    self.sortEdge() 
    self.node = [] 

    visited = defaultdict(lambda: False) 
    queue = [] 
    queue.append(s) 
    visited[s] = True 

    while queue: 
      s = queue.pop(0) 
      self.node.append(s) 

      for i in self.graph[s]: 
        if visited[i] == False: 
          queue.append(i) 
          visited[i] = True 

    return self.node 

def main(): 
  input = sys.stdin.readline 
  dfs = GraphDFS() 
  bfs = GraphBFS() 

  N, M, V = list(map(int, input().split())) 
  for m in range(M): 
    x, y = list(map(int, input().split())) 
    dfs.addEdge(x,y) 
    bfs.addEdge(x,y) 

  dfs_node = dfs.DFS(V) 
  bfs_node = bfs.BFS(V) 

  print(' '.join(list(map(str, dfs_node)))) 
  print(' '.join(list(map(str, bfs_node)))) 

main() 

https://www.acmicpc.net/problem/2753

문제

연도가 주어졌을 때, 윤년이면 1, 아니면 0을 출력하는 프로그램을 작성하시오.

윤년은 연도가 4의 배수이면서, 100의 배수가 아닐 때 또는 400의 배수일 때 이다.

예를들어, 2012년은 4의 배수라서 윤년이지만, 1900년은 4의 배수이지만, 100의 배수이기 때문에 윤년이 아니다.

하지만, 2000년은 400의 배수이기 때문에 윤년이다.

입력

첫째 줄에 연도가 주어진다. 연도는 1보다 크거나 같고, 4000보다 작거나 같은 자연수이다.

출력

첫째 줄에 윤년이면 1, 아니면 0을 출력한다.

해결 방안

1. 문제의 조건을 먼저 정리하여 자연수 n이 윤년이지 확인하는 함수를 만든다.

1-1. 400의 배수이면 윤년이다.

1-2. 400의 배수가 아닌 경우에 100의 배수이면 윤년이 아니다.

1-3. 100의 배수가 아닌 경우에 4의 배수이면 윤년이다.

1-4. 4의 배수가 아니면 윤년이 아니다.

소스 코드

import sys
input = sys.stdin.readline
N = int(input())

def isEunnen(n):
    if n % 400 == 0:
        return True
    elif n % 100 == 0:
        return False
    elif n % 4 == 0:
        return True
    return False

if isEunnen(N):
    print(1)
else:
    print(0)

https://www.acmicpc.net/problem/2588

문제

(세 자리 수) × (세 자리 수)는 다음과 같은 과정을 통하여 이루어진다.

(1)과 (2)위치에 들어갈 세 자리 자연수가 주어질 때 (3), (4), (5), (6)위치에 들어갈 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 (1)의 위치에 들어갈 세 자리 자연수가, 둘째 줄에 (2)의 위치에 들어갈 세자리 자연수가 주어진다.

출력

첫째 줄부터 넷째 줄까지 차례대로 (3), (4), (5), (6)에 들어갈 값을 출력한다.

해결 방안

1. 두 자연수를 X, Y로 문자 입력을 받아서 Y의 뒷자리 수부터 차례대로 X와 곱한 값을 (3),(4),(5)를 구한 후 더하여 (6)을 구한다.

2. (3) = int(X) * int(Y[2])

3. (4) = int(X) * int(Y[1])

4. (5) = int(X) * int(Y[0])

5. (6) = (3) + (4)*10 + (5)*100

소스 코드

import sys
input = sys.stdin.readline
X = input().strip()
Y = input().strip()

v3 = int(X) * int(Y[2])
v4 = int(X) * int(Y[1])
v5 = int(X) * int(Y[0])
v6 = v3 + v4*10 + v5*100
print(v3)
print(v4)
print(v5)
print(v6)