SWEA 4193번 D4 수영대회 결승전 ( 완전 탐색 + 구현 ) C++, 파이썬

리뷰1

BFS를 사용해 문제를 풀었다!

문제 풀이

1. 테스트 케이스의 개수를 받아와 FOR문을 개행하고 배열의 크기 N을 받아와 N*N크기의 벡터에 값을 채워준다.
2. 시작 지점과 도착 지점을 입력받아 시작 지점을 (x, y, 0)의 튜플로 만들어 준다, 4방향 리스트도 전역으로 초기화.
3. bfs의 인자로 만들어둔 튜플과 도착 지점의 x, y좌표를 넘겨준다. 나머지는 전역변수로 활용해준다.
4. 받아온 튜플을 큐에 삽입하고 while루프를 실행한다.
5. 큐의 제일 앞 데이터를 꺼내 x, y, time으로 초기화 해준다, 만약 목표 지점에 도착했으면 time을 return
6. 4방향 리스트를 돌면서 다음 좌표를 갱신한다. 범위를 넘어가지 않을 경우 2가지 경우에 대해 따로 처리해 준다.
7. 다음 좌표가 0일 경우 해당 위치를 시간 + 1값으로 할당하고 큐에 다음 위치와 time에 1을 더한 값을 튜플로 추가한다.
8. 다음 좌표가 2일 경우 소용돌이를 돌파할 수 있는 time일 경우 다음 좌표로 이동(벡터의 값은 최신화 하지 않는다.)
9. 소용돌이를 돌파할 수 없는 경우 현재 좌표를 큐에 다시 추가하되 시간은 1 추가한다.
10. while루프가 종료되면 -1을 return 해준다. 이는 목표 지점에 도착할 수 없는 경우이다.
11. return 받은 값을 각 테스트 케이스와 함께 출력 해주면 된다.

 

참고 사항

소용돌이를 돌파할 수 있을 경우는 소용돌이를 대기하는 시간 2 + 건널 수 있는 시간 1을 더한 값 3을 time에서 나눈 후 나머지가 2일 경우이다.

SWEA에서 해당 문제는 파이썬 제출이 불가능하다.

 

정답 코드

C++ 코드

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

int t, n;
vector<vector<int>> lst;
vector<pair<int, int>> dist = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

int bfs(tuple<int, int, int> start, int ax, int ay) {
	queue<tuple<int, int, int>> q;
	q.push(start);
	while (!q.empty()) {
		int x = get<0>(q.front()), y = get<1>(q.front()), time = get<2>(q.front());
		q.pop();
		if (x == ax && y == ay) {
			return time;
		}
		int nx, ny;
		for (int i = 0; i < dist.size(); i++) {
			nx = x + dist[i].first;
			ny = y + dist[i].second;
			if (0 <= nx && nx < n && 0 <= ny && ny < n) {
				if (lst[nx][ny] == 0) {
					lst[nx][ny] = time + 1;
					q.push(make_tuple(nx, ny, time + 1));
				}
				if (lst[nx][ny] == 2) {
					if (time % 3 == 2) {
						q.push(make_tuple(nx, ny, time + 1));
					}
					else {
						q.push(make_tuple(x, y, time + 1));
					}
				}
			}
		}
	}
	return -1;
}

int main() {
	cin >> t;
	for (int c = 1; c <= t; c++) {
		cin >> n;
		lst.clear();
		lst.resize(n, vector<int>(n));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> lst[i][j];
			}
		}
		int sx, sy, ax, ay;
		cin >> sx >> sy >> ax >> ay;
		tuple<int, int, int> start = make_tuple(sx, sy, 0);
		cout << "#" << c << " " << bfs(start, ax, ay) << "\n";
	}
}

 

파이썬 코드

from collections import deque


def bfs(start):
    q = deque([start])
    while q:
        x, y, time = q.popleft()
        if x == ax and y == ay:
            return time
        for dx, dy in dist:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n:
                if lst[nx][ny] == 0:
                    lst[nx][ny] = time + 1
                    q.append((nx, ny, time + 1))
                if lst[nx][ny] == 2:
                    if time % 3 == 2:
                        q.append((nx, ny, time + 1))
                    else:
                        q.append((x, y, time + 1))
    return -1


t = int(input())
for i in range(1, t + 1):
    n = int(input())
    lst = [list(map(int, input().split())) for _ in range(n)]
    dist = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    sx, sy = map(int, input().split())
    ax, ay = map(int, input().split())
    print(f'#{i} {bfs((sx, sy, 0))}')