BFS/DFS 다시..
백준 6118
결국 돌아왔다.. BFS로.
import sys
from collections import deque
N,M = map(int,sys.stdin.readline().split())
graph = [ [] for _ in range(N+1) ]
for i in range(M) :
a,b= map(int,sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
#간곳이면 0 처리
visited = [0] * (N+1)
def BFS(x):
q= deque()
q.append(x)
visited[x] = 1
while q:
comefrom = q.popleft()
for i in graph[comefrom]:
if visited[i] == 0 :
#아직 안갓따면
visited[i]= visited[comefrom]+1
q.append(i)
BFS(1)
maxnum = max(visited)
print(visited.index(maxnum),maxnum-1,visited.count(maxnum) )
해당 문제의 경우에는, 원하는 INDEX까지 가는 최소 거리끼리 비교하면 되는 문제였다.
일단 도착한 거리가 최소거리인건, BFS라는 생각을 바로 했어야했다.
그리고, VISITED를 안쓰려고했는데, 그러는것보다 일단은 사용하는것이 더욱 현명하고, TIME OVER가 났을때
변경하는 쪽으로 생각하는것이 옳겠다.
POPLEFT나, INDEX(),COUNT()는 까먹어서는안되고
FROM COLLECTIONS IMPORT DEQUE
Q = deque()도 까먹어서는 안된다.
박준 1743
import sys
sys.setrecursionlimit(1000000)
N,M,K = map(int,sys.stdin.readline().split())
trasharr = [[0]*(M+1) for _ in range(N+1) ]
for i in range(K):
r,c = map(int,sys.stdin.readline().split())
trasharr[r][c] = 1
xarr =[-1,1,0,0]
yarr =[0,0,-1,1]
def DFS(x,y):
global cnt
for i in range(4) :
nx = x+xarr[i]
ny = y+yarr[i]
if 0<nx<=N and 0<ny<=M and (trasharr[nx][ny] == 1) :
trasharr[nx][ny]=0
cnt += 1
DFS(nx,ny)
maxcnt = 0
for i in range(1,N+1) :
for j in range(1,M+1):
if trasharr[i][j] == 1:
trasharr[i][j] = 0
cnt = 1
DFS(i,j)
maxcnt = max(maxcnt,cnt)
print(maxcnt)
좀 많이 돌아간 느낌이 있다..
다 잘 해결했고, VISITED 행렬도 쓰지 않았다.
그러나 DFS를 실제 처음 호출할때, ( 기준을 다음 이동으로 맞추었기 때문에) 고려를 못하는 문제가 있었는데,
이를 처음 DFS의 ROOT 에서 시작시 잡아줬어야 했다.
기준을 명확하게 맞추고, 이에 따른 빈틈을 해결하자.
프로그래머스 게임 맵 최단 거리 파이썬
from collections import deque
def BFS(x,y,maps) :
nx = [-1,1,0,0]
ny = [0,0,-1,1]
M = len(maps)
N = len(maps[0])
q= deque()
q.append([x,y])
graph = [ [True] * N for _ in range(M)]
graph[0][0] = False
while q:
poparr = q.popleft()
xstart = poparr[0]
ystart = poparr[1]
for i in range(4) :
dx = xstart+nx[i]
dy = ystart+ny[i]
if (0<=dx<M and 0<=dy<N) and maps[dx][dy] == 1 :
if graph[dx][dy] == True :
graph[dx][dy] = False
maps[dx][dy]= maps[xstart][ystart]+1
q.append([dx,dy])
if maps[M-1][N-1] != 1 :
return maps[M-1][N-1]
else :
return -1
def solution(maps):
return BFS(0,0,maps)
BFS를 활용하여, 마지막 경로의 거리가 최단 거리인 것은 기억했지만,
1. POPLEFT를 사용했어야 한다는것
2. GRAPH를 별도로 [ [0]*N for _ in range(M)] 으로 생성했어야 한다는 것
이 두개를 기억하지 못하여 문제를 틀리고 말았다.
이 형태를 기억하자.
1 . DFS 내부에서 변경된 LIST는 반영된다
<파이썬은 매개변수로 LIST를 전달할시 해당 값의 변경이 적용된다>
import sys
sys.setrecursionlimit(1000000)
def DFS(maps,x,y,cnt):
cnt = int(maps[x][y])
dx = [-1,1,0,0]
dy = [0,0,-1,1]
maps[x][y] = 'X'
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if 0<=nx< len(maps) and 0<=ny<len(maps[0]) and maps[nx][ny] != 'X':
plus = int(maps[nx][ny])
cnt += DFS(maps,nx,ny,cnt+plus)
return cnt
def solution(maps):
answer = []
realmaps = []
for i in range(len(maps)) :
realmaps.append(list(maps[i]))
for i in range(len(realmaps)) :
for j in range(len(realmaps[0])):
if realmaps[i][j] != 'X':
an = DFS(realmaps,i,j,int(realmaps[i][j]))
if an == 0 :
continue
else:
answer.append(an)
print(realmaps)
if len(answer) == 0 :
return [-1]
else :
return sorted(answer)
해당 코드에서, DFS 내부에서 변경한 REALMAPS의 변경이 실제로 이루어짐을 볼 수 있다. (리스트가 변수일 때만)
2. CNT는, 매개변수로 넘기지만 선언으로 초기화도 진행해야 한다.
1. 선언 cnt = int(maps[x][y])
2. 매개변수로 넘겨주기 + cnt에 그 값을 저장하기 cnt += DFS(maps,nx,ny,cnt+plus)
3. return cnt -> 가장 마지막 cnt의 return 값이 그 함수를 호출한 dfs의 cnt에 추가되고 -> 추가 -> 추가.