"""
case 1 (정석)
특정의 여러 원소 제거하기
"""
 
#arr = [0, 1, 2, 3, 3, 5, 3, 7, 8, 9, 3, 9]
arr = ['0', '1', '2', '3', '3', '5', '3', '7', '8', '9', '3', '9', 'q', 'a']
remove_set = ('3', '9', 'a')  #집합자료형
 
res = [i for i in arr if i not in remove_set]
 
print(res)
 
 
"""
case 2 
1) arr에 숫자(int)만 있을 경우는 
len(arr)만큼 for로 remove로 계속 돌린다.
2) arr에 string 만 있을 경우는
문자열을 ascii code 변환 후, 계산하고, 다시 문자열로 변경
찾을 값을 ord(str)로 변경하고, for로 ord 값을 변경후, 찾고, 다시 for로 chr(int)로 변경하여 출력함
 
 
"""
"""
a = ord('a')
#print(ord('3'))
#arr=[0,1,2,3,3,5,3,7,8,9,3]
arr = ['0', '1', '2', '3', '3', '5', '3', '7', '8', '9', '3', 'q', 'a']
arr1 = [0] * len(arr)
 
for i in range(len(arr)):
  arr[i] = ord(arr[i])
#  arr1.append(int(arr[i]))
 
print(arr)
#print(arr1)
#print(arr1, 'len=', len(arr1))
 
print('count=', arr.count(a))
 
for _ in range(arr.count(a)):  #range(len(arr)):
  arr.remove(a)
 
for i in range(len(arr)):
  arr[i] = chr(arr[i])
 
print(arr, 'len=', len(arr))
"""
저작자표시

o DFS 유형

n, m = map(int, input().split())

 

graph = []

for i in range(n):

 graph.append(list(map(int, input())))

 

res = 0

 

dx = [0, 0, -1, 1]

dy = [1, -1, 0, 0]

 

def dfs(x, y):

  if(x <= -1 or x >= n or y <= -1 or y >= m):

   return False

 

  ifgraph[x][y] == 0:

   graph[x][y] = 1

 

   for i in range(4):

     dfs(x+dx[i],y+dy[i])

   return True

 

 return False

 

for i in range(n):

 for j in range(m):

   if dfs(i, j) == True:

     res += 1

 

print(res)

 

예제) 4 5

00110

00011

11111

00000  

 #답3

저작자표시

o BFS

 

from collections import deque

 

n, m = map(int, input().split())

graph = []

for i in range(n):

 graph.append(list(map(int, input())))

 

dx = [0, 0, -1, 1] #상하좌우 순서임 x라서 좌우만

dy = [1, -1, 0, 0]

 

def BFS(x, y):

 queue = deque()

 queue.append((x, y))

 

 while queue:

   x, y = queue.popleft()

 

   for i in range(4):

     nx = x + dx[i]

     ny = y + dy[i]

 

     if (nx < 0 or ny < 0 or nx >= n or ny >= m):

       continue

 

     if (graph[nx][ny] == 0):

       continue

 

 

     if (graph[nx][ny] == 1):

       graph[nx][ny] = graph[x][y] + 1

       queue.append((nx, ny))

 return graph[n - 1][m - 1]

print(BFS(0, 0)) #답 10

 

ex) 5 6

101010

111111

000011

111111

111111

저작자표시

import math

 
res0=math.factorial(5) -->120 : factorial
res1=math.gcd(10,5,100) --> 5 : 최대 공약수
res2=math.lcm(10,5,100) --> 100 : 최소 공배수
 
res3=math.ceil(2.2) -> 3 : 올림
      math.ceil(2.0) -> 2
res4=math.floor(2.7) -> 2 : 내림
      math.floor(-3.2) -> -4
 
res5=math.pow(2,4) -> 2의 4승 = 16
res7=math.sqrt(16) -> 4
저작자표시

- ValueError

 
- IndexError --> Out-of-range인 경우로 대부분 초기화하면 됨
a=[0]*(n+1)
 
- SyntaxError
 
- NameError
 
- ZeroDivisionError
 
- TypeError
 
- AttributeError
 
- KeyError -> Dict에서 Key 없음
저작자표시
from collections import deque
 
graph=[
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]
 
def DFS(graph,v,visited):
  visited[v]=True
  print(v,end=' ')
  for i in graph[v]:
    if visited[i] != True:
      visited[i]=True
      DFS(graph,i,visited)
 
def BFS(graph, v0, visited):
  queue=deque([v0])
  visited[v0]=True
 
  while queue:
    v1=queue.popleft()
    print(v1, end=' ')
    for i in graph[v1]:
      if visited[i] != True:
        queue.append(i)
        visited[i]=True
  
 
 
visited=[False]*9
 
print('DFS=')
DFS(graph,1,visited)
print('')
print('BFS=')
BFS(graph,1,visited)
 
 

o BFS (Breadth First Search)

 
from collections import deque
 
visited = [0]*(n+1)
 
def BFS(graph, v, visited):
  q=deque([v])
  visited[v]=True
  while q:
    v=q.popleft()
    print(v, end=" ")
    for i in graph[v]:
      if visited[v]!=True:
        q.append[i]
        visited[i]=True
 
BFS(graph, 1, visited)
 
 
o DFS (Depth First Search)
 
visited = [0]*(n+1)
 
def DFS(graph, v, visited):
  visited[v]=True
  print[v, end=" "]
  for i in graph[v]:
    if not in graph[v]:
      def(graph, i, visited)
저작자표시

+ Recent posts

티스토리툴바