64.등산경로(DFS)
등산을 매우 좋아하는 철수는 마을에 있는 뒷산에 등산경로를 만들 계획을 세우고 있습니다. 마을 뒷산의 형태를 나타낸 지도는 N*N 구역으로 나뉘어져 있으며, 각 구역에는 높이가 함께 나타나 있습니다.N=5이면 아래와 같이 표현됩니다.
2 23 92 78 93
59 50 48 90 80
30 53 70 75 96
94 91 82 89 93
97 98 95 96 100
어떤 구역에서 다른 구역으로 등산을 할 때는 그 구역의 위, 아래, 왼쪽, 오른쪽 중 더 높은구역으로만 이동할 수 있도록 등산로를 설계하려고 합니다. 등산로의 출발지는 전체 영역에서가장 낮은 곳이고, 목적지는 가장 높은 곳입니다. 출발지와 목적지는 유일합니다.
지도가 주어지면 출발지에서 도착지로 갈 수 있는 등산 경로가 몇 가지 인지 구하는 프로그램을 작성하세요.
▣ 입력설명
첫 번째 줄에 N(5<=N<=13)주어지고, N*N의 지도정보가 N줄에 걸쳐 주어진다.
▣ 출력설명
등산경로의 가지수를 출력한다.
▣ 입력예제 1
5
2 23 92 78 93
59 50 48 90 80
30 53 70 75 96
94 91 82 89 93
97 98 95 96 100
▣ 출력예제 1
5
내 코드
def dfs(v):
global cnt
if v==e[0]:
cnt+=1
else:
for i in range(4):
x=v[0]+dx[i]
y=v[1]+dy[i]
if 0<=x<=n-1 and 0<=y<=n-1 and lst[v[0]][v[1]]<lst[x][y]:
dfs((x,y))
n=int(input())
lst=[list(map(int, input().split())) for _ in range(n)]
dx=[0,1,0,-1]
dy=[-1,0,1,0]
cnt=0
s=min(map(min,lst))
s=[(i,j) for i in range(n) for j in range(n) if lst[i][j]==s]
e=max(map(max,lst))
e=[(i,j) for i in range(n) for j in range(n) if lst[i][j]==e]
dfs(s[0])
print(cnt)미로탐색의 가지수를 구하는 것과 마찬가지로 상하좌우로 뻗어나가며 조건에 맞을 때만 재귀함수를 실행하도록 했다. 푸는 과정 자체는 기존 DFS와 차이가 없었지만 출발점과 도착점이 입력에 따라 달라 좌표를 찾는데 고생했다. 또한 별 생각 없이 푼 부분인데, 이번 문제는 항상 큰 값으로만 이동하기 때문에 그 전 좌표를 방문했다는 체크를 하지 않아도 된다.
풀이
def DFS(x, y):
global cnt
if x==ex and y==ey:
cnt+=1
else:
for k in range(4):
xx=x+dx[k]
yy=y+dy[k]
if 0<=xx<n and 0<=yy<n and ch[xx][yy]==0 and board[xx][yy]>board[x][y]:
ch[xx][yy]=1
DFS(xx, yy)
ch[xx][yy]=0
if __name__=="__main__":
n=int(input())
board=[[0]*n for _ in range(n)]
ch=[[0]*n for _ in range(n)]
max=-2147000000
min=2147000000
for i in range(n):
tmp=list(map(int, input().split()))
for j in range(n):
if tmp[j]<min:
min=tmp[j]
sx=i
sy=j
if tmp[j]>max:
max=tmp[j]
ex=i
ey=j
board[i][j]=tmp[j]
ch[sx][sy]=1
cnt=0
DFS(sx, sy)
print(cnt)반성점
- map함수를 제대로 알고 사용하지 못하고 있었다.
배운 것
- max/min함수를 그저 최대/최소값을 구하는 함수로만 알고 있어서 2차원 리스트에 이 함수를 쓰면 알아서 전체 원소들 중 최대/최소를 찾아주는 줄 알았다. 하지만 뭔가 이상해서 찾아보니 2차원 리스트일 경우 각 행의 합으로 최대/최소를 판단하기 때문에 예상했던 값이 나오지 않을 수 있다. 따라서 2차원 리스트에서 최대/최소값을 구하려면 map함수를 사용해
max(map(max,list))처럼 구해야 한다. - map함수를 지금까지 입력 받을 때 나눠서 받게 하는 정도로만 쓰고 정확한 원리는 몰랐는데, 제대로 알고 쓰면 더 폭넓게 쓸 수 있다는 것을 이번 문제를 통해 배웠다.
map함수는 그 안에 함수와 iterable객체를 인자로 받는다. 그래서 객체 하나하나에 인자로 받은 함수를 적용해주는데, 이 원리를 통해 2차원 리스트의 최대/최소값을 구할 수 있다.
max(map(max,list))를 보면 2차원 리스트의 각 행에 max함수를 실행하는 것과 같다. 그래서 map은 각 행의 최대값을 받고, 거기에 다시 max함수를 실행함으로써 각 행의 최대값 중 최대값(=전체의 최대값)을 찾을 수 있는 것이다.
